Tài liệu Kỹ thuật phân cụm dữ liệu không gian có ràng buộc

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG CHU THỊ HẢO KỸ THUẬT PHÂN CỤM DỮ LIỆU KHÔNG GIAN CÓ RÀNG BUỘC LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN, 2017 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG CHU THỊ HẢO KỸ THUẬT PHÂN CỤM DỮ LIỆU KHÔNG GIAN CÓ RÀNG BUỘC 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. ĐẶNG VĂN ĐỨC THÁI NGUYÊN, 2017 i MỤC LỤC MỞ ĐẦU .......................................................................................................... 1 Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ DỮ LIỆU KHÔNG GIAN ................................................................................................ 4 1.1. Khai phá dữ liệu ......................................................................................... 4 1.1.1. Một số khái niệm ..................................................................................... 4 1.1.2. Quá trình khai phá dữ liệu....................................................................... 4 1.1.3. Các kỹ thuật khai phá dữ liệu.................................................................. 7 1.2. Dữ liệu không gian địa lý ........................................................................... 9 1.3. Hệ thống thông tin địa lý và ứng dụng..................................................... 10 1.3.1. Một số định nghĩa về hệ thông tin địa lý .............................................. 11 1.3.2. Mô hình biểu diễn dữ liệu địa lý không gian ........................................ 14 1.3.3. Quan hệ không gian giữa các đối tượng địa lý ..................................... 20 1.4. Khái niệm và mục tiêu của Phân cụm dữ liệu ......................................... 20 1.5. Kết luận .................................................................................................... 23 Chương 2. MỘT SỐ KỸ THUẬT PHÂN CỤM DỮ LIỆU KHÔNG GIAN...24 2.1. Phương pháp phân cụm theo phân hoạch ............................................... 24 2.2. Phương pháp phân cụm dựa trên mật độ ................................................. 26 2.3. Phương pháp phân cụm dựa trên lưới ...................................................... 32 2.4. Phương pháp phân cụm dữ liệu ràng buộc............................................... 35 2.4.1. Thuật toán phân cụm dữ liệu không gian .............................................. 37 2.4.2. Thuật toán .............................................................................................. 45 2.5. Kết luận .................................................................................................... 48 Chương 3. CÀI ĐẶT VÀ THỬ NGHIỆM .................................................. 49 3.1. Phân tích bài toán ..................................................................................... 49 3.1.1. Nguồn dữ liệu đầu vào và phạm vi bài toán ......................................... 49 3.1.2. Phương pháp kỹ thuật giải quyết bài toán............................................. 50 ii 3.2. Xây dựng chương trình ứng dụng ............................................................ 51 3.2.1. Phân tích thiết kế hệ thống .................................................................... 51 3.2.2. Cài đặt chương trình .............................................................................. 52 3.3. Thử nghiệm và đánh giá các thuật toán phân cụm................................... 54 KẾT LUẬN VÀ KIẾN NGHỊ ...................................................................... 61 TÀI LIỆU THAM KHẢO ............................................................................ 62 iii DANH MỤC CÁC BẢNG Bảng 3.1: So sánh tổng quan các thuật toán K-means, DBSCAN và DBRS ...... 54 Bảng 3.2: Kết quả so sánh thời gian thực hiện phân cụm của các thuật toán K-means, DBSCAN và DBRS với cùng một tập dữ liệu đầu vào...... 56 Bảng 3.3: Kết quả so sánh thời gian thực hiện phân cụm của các thuật toán K-means, DBSCAN và DBRS trên các tập dữ liệu khác nhau ........... 57 iv DANH MỤC CÁC HÌNH Hình 1.1: Khai phá dữ liệu trong tập dữ liệu ....................................................... 4 Hình 1.2: Tiến trình khám phá tri thức từ cơ sở dữ liệu ..................................... 5 Hình 1.3: Kiến trúc điển hình của một hệ khai phá dữ liệu ............................... 6 Hình 1.4. Ví dụ biểu diễn vị trí trước bị ô nhiễm .............................................. 13 Hình 1.5. Ví dụ biểu diễn đường xác định bởi ranh giới các đường, có điểm đầu trùng với điểm cuối.............................................................. 13 Hình 1.6: Ví dụ biểu diễn khu vực hành chính .................................................. 14 Hình 1.7: Biểu diễn vector của đối tượng địa lý ................................................ 18 Hình 1.8: Biểu diễn thế giới bằng mô hình raster.............................................. 19 Hình 1.9: Mô tả tập dữ liệu được phân thành 3 cụm ........................................ 21 Hình 2.1: Minh họa thuật toán k-means .............................................................. 25 Hình 2.2: Kề mật độ ................................................................................................ 27 Hình 2.3: Kết nối theo mật độ ............................................................................... 27 Hình 2.4: Hình dạng các cụm được khám phá bởi thuật toán DBSCAN ...... 28 Hình 2.5: Cấu trúc phân cấp .................................................................................. 32 Hình 2.3: Các cách mà các cụm có thể đưa ra ................................................... 36 Hình 2.6: Phân cụm các đối tượng dữ liệu ràng buộc. ..................................... 37 Hình 2.7: Phân cụm các đối tượng dữ liệu ràng buộc....................................... 40 Hình 2.8: Các đa giác đơn giản và tạo ra các đường cản trở ........................... 44 Hình 2.9: Thuật toán 1: phân cụm có các ràng buộc......................................... 47 Hình 2.10: Thuật toán 2: Mở rộng một cụm ......................................................... 47 Hình 2.11: Tìm các điểm láng giềng ...................................................................... 47 Hình 3.1: Phân cu ̣m lớp dữ liê ̣u "Khách sa ̣n-Trường học trong nô ̣i thành Hà Nô ̣i, các vùng màu vàng là các cu ̣m tìm đươ ̣c. ............... 53 v Hình 3.2: Hình ảnh chồng phủ (vùng màu vàng) của các cụm “Siêu thi”̣ (màu xanh) và các cu ̣m “Khách sa ̣n- Trường học” (màu đỏ). Vùng màu vàng có thể coi là vị trí tối ưu cho việc đă ̣t địa điể m Nhà hàng. ...................................................................................... 53 Hình 3.3: Kết quả phân cụm DBSCAN đối với dữ liệu thử nghiệm tự tạo...... 54 Hình 3.4: Khả năng phát hiện nhiễu và cụm có hình dạng bất kỳ của Kmeans (trái) và DBSCAN (phải), đường bao màu xanh là đường biên cụm ..................................................................................... 55 Hình 3.5: Khả năng phân cụm theo thuộc tính của DBSCAN (trái) và DBRS (phải) ........................................................................................... 55 Hình 3.5: Đồ thị so thời gian thực hiện phân cụm của các thuật toán Kmeasn, DBSCAN và DBRS với cùng một tập dữ liệu đầu vào. ........ 57 Hình 3.6: Phân cụm tập dữ liệu DS1 ................................................................... 59 Hình 3.7: Phân cụm DS2 ........................................................................................ 60 1 MỞ ĐẦU Hệ thống thông tin địa lý (GIS) được ứng dụng ngày càng phổ biến, không chỉ trong lĩnh vực giám sát, quản lý, lập kế hoạch về tài nguyên môi trường mà còn trong nhiều bài toán kinh tế xã hội khác. Kết quả là, khối lượng dữ liệu liên quan đến địa lý, còn gọi là dữ liệu không gian thu thập được tăng lên nhanh chóng. Một câu hỏi đặt ra là làm thế nào để tận dụng, khai thác, khám phá, phát hiện những tri thức hữu ích từ kho dữ liệu này? Khai phá dữ liệu là áp dụng các kỹ thuật và công cụ để trích rút các tri thức có ích từ nguồn dữ liệu về một lĩnh vực nào đó mà ta quan tâm. Khai phá dữ liệu với GIS hay còn gọi là khai phá dữ liệu không gian, mở rộng khai phá dữ liệu trong các CSDL quan hệ, xét thêm các thuộc tính của dữ liệu không gian được phản ánh trong hệ thông tin địa lý, ví dụ khoảng cách (gần kề hay cách xa), điều kiện môi trường tự nhiên hay kinh tế xã hội (rừng núi, đồng bằng, ven biển, đô thị, v.v…). Các bài toán truyền thống của một hệ thông tin địa lý có thể trả lời các câu hỏi kiểu như: - Những con phố nào dẫn đến sân bay Tân Sân Nhất ? - Những căn nhà nào nằm trong vùng quy hoạch mở rộng phố? Khai phá dữ liệu không gian có thể giúp trả lời cho các câu hỏi dạng: - Xu hướng của các dòng chảy, các đứt gãy địa tầng ? - Nên bố trí các trạm tiếp sóng điện thoại di động như thế nào? - Những vị trí nào là tối ưu để đặt các máy ATM, xăng dầu, nhà hàng,…? Một trong những bài toán liên quan đến dữ liệu không gian, cụ thể là dữ liệu địa lý có ý nghĩa thực tế cao là bài toán xác định vị trí tối ưu cho việc đặt các cây xăng. Cả nước hiện có 374 tổng đại lý và hơn 14.000 cửa hàng bản lẻ xăng dầu. Để xác định được vị trí đặt các trạm bán lẻ xăng dầu cần 2 phải tuân theo các quy định của Bộ Công thương, nhất là các quy định về an toàn, phòng chống cháy nổ. Ngoài ra, cây xăng cũng phải đặt ở vị trí thuận lợi cho việc kinh doanh đạt doanh số cao. Hoặc một bài toán khác cũng có ý nghĩa thực tiễn rất lớn đó là xác định vị trí tối ưu để mở một nhà hàng. Hiện nay trên địa bàn thành phố Hà Nội cũng đã có rất nhiều nhà hàng, quán ăn đã được mở ra. Nhưng không phải tất cả các nhà hàng, quán ăn đó đều có thể cho doanh thu tốt. Có khi có nhà hàng mới mở ra được một thời gian ngắn đã phải đóng cửa vì không có khách dẫn đến chủ đầu tư phải chịu thua lỗ nặng. Một trong những nguyên nhân chính dẫn đến thất bại đó là địa điểm kinh doanh chưa hợp lý. Một vị trí tối ưu cho việc mở nhà hàng, quán ăn thì vị trí đó phải thỏa mãn một số yếu tố sau: nằm trong khu vực đông dân cư, gần nhiều cơ quan công sở hay trường học, có khu vực để xe, có quang cảnh xung quanh thoáng mát...các vấn đề này đã được rất nhiều các đề tài nghiên cứu tuy nhiên với những vị trí phức tạp có các ngăn cách con sông hay cây cầu v.v… thì cần phải có những đánh giá chính xác hơn nữa. Xuất phát từ nhu cầu thực tế đó và do đặc thù, khả năng ứng dụng rất phong phú của kỹ thuật phân cụm dữ liệu trong không gian nên em đã chọn nghiên cứu đề tài kỹ thuật phân cụm dữ liệu không gian có ràng buộc làm luận văn tốt nghiệp cao học. Trên cơ sở đó cài đặt thử nghiệm một ứng dụng sử dụng kỹ thuật phân cụm dữ liệu không gian, trong đó khai thác thông tin địa lý của các đối tượng để hỗ trợ giải quyết bài toán ví dụ như tìm vị trí tối ưu đặt nhà hàng. Luận văn được chia thành các chương mục sau - Chương 1: Tổng quan về khai phá dữ liệu và dữ liệu không gian - Chương 2: Một số kỹ thuật phân cụm dữ liệu không gian - Chương 3: Xây dựng chương trình thử nghiệm, kết luận, đánh giá 3 Luận văn này được hoàn thành dưới sự hướng dẫn tận tình của PGS.TS Đặng Văn Đức, em xin bày tỏ lòng biết ơn chân thành của mình đối với thầy. Em xin chân thành cảm ơn các thầy, cô giáo Viện Công nghệ thông tin, Trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên đã tham gia giảng dạy, giúp đỡ em trong suốt qúa trình học tập nâng cao trình độ kiến thức. Tuy nhiên vì điều kiện thời gian và khả năng có hạn nên luận văn không thể tránh khỏi những thiếu sót. Em kính mong các thầy cô giáo và các bạn đóng góp ý kiến để đề tài được hoàn thiện hơn 4 Chương 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ DỮ LIỆU KHÔNG GIAN 1.1. Khai phá dữ liệu 1.1.1. Một số khái niệm 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ê). Hình 1.1 minh họa đơn giản và trực quan cho khái niệm này. Hình 1.1: Khai phá dữ liệu trong tập dữ liệu [5] Khám phá tri thức trong CSDL là lĩnh vực liên quan đến nhiều ngành như: Tổ chức dữ liệu, xác suất, thống kê, lý thuyết thông tin, học máy, CSDL, thuật toán, trí tuệ nhân tạo, tính toán song song và hiệu năng cao. Các kỹ thuật chính áp dụng trong khám phá tri thức phần lớn được thừa kế từ các ngành này. 1.1.2. Quá trình khai phá dữ liệu Một số nhà khoa học xem khai phá dữ liệu là một cách gọi khác của một thuật ngữ rất thông dụng: Khám phá tri thức từ cơ sở dữ liệu (Knowledge Discovery in Database- KDD). Mặt khác, khi chia các bước trong quá trình khám phá tri thức, một số nhà nghiên cứu lại cho rằng, KPDL chỉ là một bước trong quá trình khám phá tri thức [5]. 5 Như vậy, khi xét ở mức tổng quan thì hai thuật ngữ này là tương đương nhau, nhưng khi xét cụ thể thì KPDL được xem là một bước trong quá trình khám phá tri thức. Nhìn chung, khai phá dữ liệu hay khám phá tri thức từ cơ sở dữ liệu bao gồm các bước sau [4]: Hình 1.2: Tiến trình khám phá tri thức từ cơ sở dữ liệu Trích chọn dữ liệu: Là quá trình trích lọc một lượng dữ liệu phù hợp, cần thiết từ tập dữ liệu lớn (cơ sở dữ liệu tác nghiệp, kho dữ liệu)… Tiền xử lý dữ liệu: Là bước làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, ngoại lai, dữ liệu không nhất quán…), rút gọn dữ liệu (lấy mẫu dữ liệu, lượng tử hóa…), rời rạc hóa dữ liệu. Kết quả sau bước này là dữ liệu có tính nhất quán, đầy đủ, được rút gọn và được rời rạc hóa. Chuyển đổi dữ liệu: Là bước chuẩn hóa khuôn dạng và làm mịn dữ liệu, nhằm đưa dữ liệu về dạng thuận lợi nhất để phục vụ cho việc áp dụng các giải thuật khai phá dữ liệu ở bước sau. Khai phá dữ liệu: Sử dụng các phương pháp, kỹ thuật, các thuật toán để trích lọc ra mẫu có ý nghĩa cùng với các tri thức, quy luật, biểu thức mô tả mối quan hệ của dữ liệu trong một khía cạnh nào đó. Đây là bước quan trọng và tốn nhiều thời gian nhất của toàn bộ tiến trình KDD. 6 Đánh giá và biểu diễn tri thức: Trình bày các tri thức, quy luật, biểu thức có ý nghĩa đã tìm được ở bước trước dưới các dạng thức gần gũi, dễ hiểu đối với người sử dụng như đồ thị, biểu đồ, cây, bảng biểu, luật…Đồng thời đưa ra những đánh giá về tri thức khám phá được theo những tiêu chí nhất định. Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của con người để điều chỉnh cách thức và kỹ thuật sử dụng trong khai phá, nhằm thu được tri thức phù hợp nhất. Dựa trên các bước của quá trình khai phá dữ liệu như trên, kiến trúc điển hình của một hệ khai phá dữ liệu có thể bao gồm các thành phần như sau: Hình 1.3: Kiến trúc điển hình của một hệ khai phá dữ liệu 7 1.1.3. Các kỹ thuật khai phá dữ liệu Trong thực tế có nhiều kỹ thuật khai phá dữ liệu khác nhau nhằm thực hiện hai chức năng mô tả và dự đoán. Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Một số kỹ thuật khai phá trong nhóm này là: phân cụm dữ liệu (Clustering), tổng hợp (Summarisation), trực quan hoá (Visualization), phân tích sự tiến hóa (Evolution and deviation analyst),…. Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên cơ sở dữ liệu hiện thời. Một số kỹ thuật khai phá trong nhóm này là: phân lớp (Classification), hồi quy (Regression), cây quyết định (Decision tree), thống kê (statictics), mạng nơron (neural network), luật kết hợp,…. Một số kỹ thuật phổ biến [1],[3],[5] thường được sử dụng để khai phá dữ liệu hiện nay là: 1.1.3.1. Phân lớp dữ liệu Mục tiêu của phân lớp dữ liệu đó là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình gồm hai bước: xây dựng mô hình, sử dụng mô hình để phân lớp dữ liệu (mỗi mẫu 1 lớp). Mô hình được sử dụng để dự đoán nhãn lớp khi mà độ chính xác của mô hình chấp nhận được. 1.1.3.2. Phân cụm dữ liệu Mục tiêu của phân cụm dữ liệu là 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 thuộc cùng một cụm là tương đồng. Trong luận này tác giả đã sử dụng kỹ thuật phân cụm và thuật toán DBSCAN DBCLUC tìm vị trí thích hợp để đặt nhà hàng. Vì vậy kỹ thuật này và các thuật toán có liên quan sẽ được trình bày trong chương II. 8 1.1.3.3. Khai phá luật kết hợp Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Đầu ra của giải thuật luật kết hợp là tập luật kết hợp tìm được. Phương pháp khai phá luật kết hợp gồm có hai bước: Bước 1: Tìm ra tất cả các tập mục phổ biến. Một tập mục phổ biến được xác định thông qua tính độ hỗ trợ và thoả mãn độ hỗ trợ cực tiểu. Bước 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải thoả mãn độ hỗ trợ và độ tin cậy cực tiểu. 1.1.3.4. Hồi quy Phương pháp hồi quy tương tự như là phân lớp dữ liệu. Nhưng khác ở chỗ nó dùng để dự đoán các giá trị liên tục còn phân lớp dữ liệu dùng để dự đoán các giá trị rời rạc. 1.1.3.5. Mạng nơ-ron (neural network) Đây là một trong những kỹ thuật KPDL được ứng dụng phổ biến hiện nay. Kỹ thuật này phát triển dựa trên một nền tảng toán học vững vàng, khả năng huấn luyện trong kỹ thuật này dựa trên mô hình thần kinh trung ương của con người. Kết quả mà mạng nơ-ron học được có khả năng tạo ra các mô hình dự báo, dự đoán với độ chính xác và độ tin cậy cao. Nó có khả năng phát hiện ra được các xu hướng phức tạp mà kỹ thuật thông thường khác khó có thể phát hiện ra được. Tuy nhiên phương pháp neural network rất phức tạp và quá trình tiến hành nó gặp rất nhiều khó khăn: đòi hỏi mất nhiều thời gian, nhiều DL, nhiều lần kiểm tra thử nghiệm. 1.1.3.6. Cây quyết định Kỹ thuật cây quyết định là một công cụ mạnh và hiệu quả trong việc phân lớp và dự báo. Các đối tượng DL được phân thành các lớp. Các giá trị của đối tượng DL chưa biết sẽ được dự đoán, dự báo. Tri thức được rút ra 9 trong kỹ thuật này thường được mô tả dưới dạng tường minh, đơn giản, trực quan, dễ hiểu đối với người sử dụng. Trong những năm qua, nhiều mô hình phân lớp DL đã được các nhà khoa học trong nhiều lĩnh vực khác nhau đề xuất, nhưng kỹ thuật cây quyết định với những ưu điểm của mình được đánh giá là một công cụ mạnh, phổ biến và đặc biệt thích hợp cho DM nói chung và phân lớp dữ liệu nói riêng. 1.2. Dữ liệu không gian địa lý Khái niệm - Đố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ý. Một trạm xăng trên bản đồ là một thể hiện cụ thể của đối tượng địa lý trạm xăng. - 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. Cơ sở dữ liệu địa lý là một tập hợp các dữ liệu địa lý có chuẩn cấu trúc được lưu trữ trên máy tính và các thiết bị lưu trữ thông tin khác, có thể thỏa mãn yêu cầu khai thác thông tin đồng thời của nhiều người sử dụng hay nhiều chương trình ứng dụng với nhiều mục đích khác nhau. - 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. Mỗi đối tượng này chiếm một vùng không gian được đặc trưng bởi hai thuộc tính vị trí và biên. 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. Ví dụ con đường có thể có 10 các thông tin như tên đường, độ rộng, chất liệu làm đường, đơn vị quản lý, thời gian đưa vào sử dụng, ... Các thuộc tính này gọi là các thông tin thuộc tính phi không gian (dữ liệu phi không gian). 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ý. GIS được hình thành vào những năm 1960 và phát triển mạnh trong 10 năm lại đây. Xét dưới góc độ hệ thống, GIS có thể được hiểu như một hệ thống gồm các thành phần: 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). Một cách đơn giản, có thể hiểu GIS như một sự kết hợp giữa bản đồ (map) và cơ sở dữ liệu (database). GIS = Bản đồ + Cơ sở dữ liệu Bản đồ trong GIS là một công cụ hữu ích cho phép chỉ ra vị trí của từng địa điểm. Với sự kết hợp giữa bản đồ và cơ sở dữ liệu, người dùng có thể xem thông tin chi tiết về từng đối tượng/thành phần tương ứng với địa điểm trên bản đồ thông qua các dữ liệu đã được lưu trữ trong cơ sở dữ liệu. Ví dụ, khi xem bản đồ về các thành phố, người dùng có thể chọn một thành phố để xem thông tin về thành phố đó như diện tích, số dân, thu nhập bình quân, số quận/huyện của thành phố, 1.3. Hệ thống thông tin địa lý và ứng dụng Khái niệm Địa lý (Geography) đề cập lĩnh vực nghiên cứu mô tả Trái đất (Geo-Earth). Ngày nay, khái niệm này và khái niệm Không gian (Space) được sử dụng thay thế nhau trong một số trường hợp. Tuy nhiên, về mặt bản chất thì Địa lý là tập các mô tả về không gian (hai chiều), khí quyển (ba chiều), … của Trái đất. Còn không gian cho phép mô tả bất kỳ cấu trúc đa chiều nào, không quan tâm đến vị trí địa lý của nó. Như vậy có thể coi Địa lý như là một phần cấu trúc nhỏ trong tập cấu trúc Không gian. 11 Khi mô tả Trái đất, các nhà địa lý luôn đề cập đến quan hệ không gian (spatial relationship) của các đối tượng trong thế giới thực. Mối quan hệ này được thể hiện thông qua các bản đồ (map) trong đó biểu diễn đồ họa của tập các đặc trưng trừu tượng và quan hệ không gian tương ứng trên bề mặt trái đất, ví dụ: bản đồ dân số biểu diễn dân số tại từng vùng địa lý. Dữ liệu bản đồ còn là loại dữ liệu có thể được số hóa. Để lưu trữ và phân tích các số liệu thu thập được, cần có sự trợ giúp của hệ thông tin địa lý (Geographic Information System-GIS). 1.3.1. Một số định nghĩa về hệ thông tin địa lý Có nhiều cách diễn giải khác nhau cho từ viết tắt GIS, tuy nhiên các cách diễn giải đó đều mô tả việc nghiên cứu các thông tin địa lý và các khía cạnh khác liên quan. GIS cũng giống như các hệ thống thông tin khác, có khả năng nhập, tìm kiếm và quản lý các dữ liệu lưu trữ, để từ đó đưa ra các thông tin cần thiết cho người sử dụng. Ngoài ra, GIS còn cho phép lập bản đồ với sự trợ giúp của máy tính, giúp cho việc biểu diễn dữ liệu bản đồ tốt hơn so với cách truyền thống. Dưới đây là một số định nghĩa GIS hay dùng [1]: Định nghĩa của dự án The Geographer's Craft, Khoa Địa lý, Trường Đại học Texas: GIS là cơ sở dữ liệu số chuyên dụng trong đó hệ trục tọa độ không gian là phương tiện tham chiếu chính. GIS bao gồm các công cụ để thực hiện những công việc sau: - Nhập dữ liệu từ bản đồ giấy, ảnh vệ tinh, ảnh máy bay, số liệu điều tra và các nguồn khác. - Lưu trữ dữ liệu, khai thác, truy vấn cơ sở dữ liệu. - Biến đổi dữ liệu, phân tích, mô hình hóa, bao gồm cả dữ liệu thống kê và dữ liệu không gian. - Lập báo cáo, bao gồm bản đồ chuyên đề, bảng biểu, biểu đồ và kế hoạch. Từ định nghĩa trên, ta thấy: Thứ nhất, GIS có quan hệ với ứng dụng cơ sở dữ liệu. Thông tin trong GIS đều liên kết với tham chiếu không gian và GIS sử dụng tham chiếu không gian như phương tiện chính để lưu trữ và truy nhập thông tin. Thứ hai, GIS là công nghệ tích hợp, cung cấp các khả năng 12 phân tích như phân tích ảnh máy bay, ảnh vệ tinh hay tạo lập mô hình thống kê, vẽ bản đồ... Cuối cùng, GIS có thể được xem như một hệ thống cho phép trợ giúp quyết định. Cách thức nhập, lưu trữ, phân tích dữ liệu trong GIS phải phản ánh đúng cách thức thông tin sẽ được sử dụng trong công việc lập quyết định hay nghiên cứu cụ thể. Định nghĩa của David Cowen, NCGIA, Mỹ GIS là hệ thống phần cứng, phần mềm và các thủ tục được thiết kế để 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 qui chiếu không gian để giải quyết các vấn đề quản lý và lập kế hoạch phức tạp. Một cách đơn giản, có thể hiểu GIS như một sự kết hợp giữa bản đồ (map) và cơ sở dữ liệu (database). GIS = Bản đồ + Cơ sở dữ liệu Bản đồ trong GIS là một công cụ hữu ích cho phép chỉ ra vị trí của từng địa điểm. Với sự kết hợp giữa bản đồ và cơ sở dữ liệu, người dùng có thể xem thông tin chi tiết về từng đối tượng/thành phần tương ứng với địa điểm trên bản đồ thông qua các dữ liệu đã được lưu trữ trong cơ sở dữ liệu. Ví dụ, khi xem bản đồ về các thành phố, người dùng có thể chọn một thành phố để xem thông tin về thành phố đó như diện tích, số dân, thu nhập bình quân, số quận/huyện của thành phố, * Ðiểm (Point) Điểm được xác định bởi cặp giá trị tọa độ (x, y). Các đối tượng đơn với thông tin về địa lý chỉ bao gồm vị trí thường được mô tả bằng đối tượng điểm. Các đối tượng biểu diễn bằng kiểu điểm thường mang đặc tính chỉ có tọa độ đơn (x, y) và không cần thể hiện chiều dài và diện tích. Ví dụ, trên bản đồ, các vị trícủa bệnh viện, các trạm rút tiền tự động ATM, các cây xăng, … có thể được biểu diễn bởi các điểm. Hình 1.1 là ví dụ về vị trí nước bị ô nhiễm. Mỗi vị trí được biểu diễn bởi 1 điểm gồm cặp tọa độ (x, y) và tương ứng với mỗi vị trí đó có thuộc tính độ sâu và tổng số nước bị nhiễm bẩn. Các vị trí này được biểu diễn trên bản đồ và lưu trữ trong các bảng dữ liệu. 13 Hình 1.4. Ví dụ biểu diễn vị trí trước bị ô nhiễm Ðường - Cung (Line - Arc) Đường được xác định bởi dãy các điểm hoặc bởi 2 điểm đầu và điểm cuối. Đường dùng để mô tả các đối tượng địa lý dạng tuyến như đường giao thông, sông ngòi, tuyến cấp điện, cấp nước… Các đối tượng được biểu diễn bằng kiểu đường thường mang đặc điểm là có dãy các cặp tọa độ, các đường bắt đầu và kết thúc hoặc cắt nhau bởi điểm, độ dài đường bằng chính khoảng cách của các điểm. Ví dụ, bản đồ hệ thống đường bộ, sông, đường biên giới hành chính, … thường được biểu diễn bởi đường và trên đường có các điểm (vertex) để xác định vị trí và hình dáng của đường. ● Vùng (Polygon) Hình 1.5: Ví dụ biểu diễn đường xác định bởi ranh giới các đường, có điểm đầu trùng với điểm cuối