Luận văn phương pháp lan truyền độ tương tự trong phân cụm dữ liệu và ứng dụng - ĐH Thái Nguyên

Luận văn thạc sĩ nghiên cứu phương pháp lan truyền độ tương tự trong phân cụm dữ liệu, ứng dụng vào khai thác dữ liệu địa lý và khí tượng.

• Tác giả: Tạ Duy Khánh
• Người hướng dẫn: PGS.TS Nguyễn Đình Hóa
• Trường học: Đại học Thái Nguyên, Trường Đại học Công nghệ Thông tin và Truyền thông
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phương pháp lan truyền độ tương tự trong phân cụm dữ liệu và ứng dụng
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CÁM ƠN
• MỤC LỤC
• DANH MỤC CÁC TỪ VIẾT TẮT
• DANH MỤC CÁC HÌNH 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Ý
• 1.1. Tổng quan về hệ thống thông tin địa lý
• 1.1.1. Lịch sử ra đời
• 1.2. Các thành phần của hệ thống thông tin địa lý
• 1.3. Dữ liệu trong hệ thống thông tin địa lý
• 1.4. Phân cụm dữ liệu địa lý
• 1.4.1. Phân cụm dữ liệu
• 2. CHƢƠNG 2: PHÂN CỤM BẰNG THUẬT TOÁN LAN TRUYỀN ĐỘ TƢƠNG TỰ
• 2.1. Các khái niệm cơ sở
• 2.2. Ý tưởng thuật toán
• 2.3. Các công thức chính trong thuật toán AP
• 2.4. Thuật toán AP nguyên thủy
• 2.5. Thuật toán lan truyền AP tự thích nghi
• 2.5.1. Phương pháp thích ứng giảm dần
• 2.5.2. Kỹ thuật thích nghi p-scanning
• 2.6. 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
• 2.6.1. Khoảng cách và ý nghĩa
• 2.6.2. Phương pháp
• 2.6.3. Cải thiện độ đo tương tự
• 2.6.4. Thích nghi thuật toán lan truyền
• 3. CHƢƠNG 3: XÂY DỰNG ỨNG DỤNG PHÂN CỤM DỮ LIỆU ĐỊA LÝ
• 3.1. Bài toán thực tế và cách tiếp cận phân cụm dữ liệu
• 3.1.1. Bài toán khai thác các dữ liệu quan trắc khí tượng
• 3.1.2. Lựa chọn giải pháp kỹ thuật công nghệ
• 3.1.3. Các phần mềm GIS
• 3.1.4. Tìm hiểu về phần mềm mã nguồn mở MapWindow
• 3.2. Thiết kế một plug-in trên phần mềm mã nguồn mở Mapwindown
• 3.2.1. Thêm một plug-ins từ Visual Studio vào MapWindow
• 3.2.2. Xây dựng ứng dụng với Active X map control trong Visual Studio
• 3.3. Kết quả chạy thử nghiệm
• 3.4. Một số kết quả đạt được của luận văn
• 3.5. Những hạn chế và hướng phát triển
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về Phân cụm dữ liệu Khám phá tri thức ẩn từ Big Data

Trong kỷ nguyên bùng nổ thông tin, khi lượng dữ liệu tăng trưởng theo cấp số nhân, việc khai phá dữ liệu để trích rút tri thức trở thành một nhiệm vụ tối quan trọng. Phân cụm dữ liệu (Data Clustering) nổi lên như một kỹ thuật cơ bản trong học không giám sát, cho phép tổ chức các đối tượng dữ liệu thành các nhóm hoặc cụm dựa trên sự tương đồng nội tại của chúng. Mục tiêu chính của phân cụm dữ liệu là phát hiện các cấu trúc tự nhiên tiềm ẩn trong tập dữ liệu lớn mà không cần thông tin nhãn trước. Quá trình này không chỉ giúp đơn giản hóa việc phân tích mà còn là bước tiền xử lý thiết yếu cho nhiều tác vụ học máy và khoa học dữ liệu phức tạp hơn.

Theo Tạ Duy Khánh (2015), "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." Sự tương tự này thường được đo bằng các hàm khoảng cách trong không gian đặc trưng của dữ liệu. Các thuật toán phân cụm được ứng dụng rộng rãi từ phân tích hành vi khách hàng trong kinh doanh, phát hiện gian lận trong tài chính, đến phân loại bệnh trong y tế và phân cụm dữ liệu địa lý trong quản lý tài nguyên. Việc lựa chọn phương pháp gom cụm dữ liệu phù hợp có thể ảnh hưởng lớn đến chất lượng tri thức được trích xuất. Đặc biệt, khi đối mặt với các tập dữ liệu có cấu trúc phức tạp hoặc không xác định rõ số lượng cụm ban đầu, các thuật toán phân cụm linh hoạt và mạnh mẽ trở nên cần thiết hơn bao giờ hết. Sự phát triển không ngừng của các phương pháp phân cụm dữ liệu tiếp tục mở ra những chân trời mới trong việc hiểu và sử dụng hiệu quả kho tàng thông tin khổng lồ hiện có.

1.1. Phân cụm dữ liệu là gì Tầm quan trọng trong Khoa học dữ liệu

Phân cụm dữ liệu là một kỹ thuật trọng tâm trong khai phá dữ liệu và học không giám sát. Nó bao gồm việc phân chia một tập hợp các đối tượng dữ liệu thành các nhóm (còn gọi là cụm) sao cho các đối tượng trong cùng một nhóm có mức độ tương đồng cao hơn so với các đối tượng thuộc các nhóm khác. Mục đích chính là khám phá cấu trúc ẩn, các mẫu hoặc mối quan hệ chưa biết trong dữ liệu lớn. Các kết quả phân cụm cung cấp cái nhìn sâu sắc về phân bố dữ liệu, giúp các nhà nghiên cứu và phân tích đưa ra quyết định dựa trên bằng chứng. Trong khoa học dữ liệu, phân cụm là một công cụ độc lập để xem xét phân bố dữ liệu, đồng thời là một bước tiền xử lý quan trọng cho các tác vụ tiếp theo như phân loại, hồi quy hoặc giảm chiều. Sự gom cụm dữ liệu hiệu quả có thể tiết lộ các phân khúc khách hàng, các loại tài liệu, hoặc các khu vực địa lý có đặc điểm chung, từ đó hỗ trợ tối ưu hóa quy trình và chiến lược.

1.2. Thách thức trong phân tích dữ liệu địa lý Vấn đề gom cụm đặc thù

Dữ liệu địa lý là một loại hình dữ liệu đặc biệt, kết hợp cả thông tin không gian (vị trí, hình dạng) và thông tin thuộc tính (đặc điểm của đối tượng tại vị trí đó). Việc phân cụm dữ liệu địa lý đặt ra nhiều thách thức riêng. Các đối tượng vùng, ví dụ như các đa giác biểu diễn khu vực, thường có hình dạng và kích thước rất đa dạng, khiến việc xác định độ đo tương tự trở nên phức tạp. Hàm khoảng cách truyền thống có thể không phản ánh đúng mối quan hệ lân cận giữa các vùng. Ngoài ra, việc kết hợp dữ liệu thuộc tính và không gian yêu cầu một phương pháp tính toán khoảng cách tổng hợp hoặc phân tách các bước gom cụm. Các điều kiện ràng buộc từ tự nhiên (sông, núi) hoặc hành chính (ranh giới hành chính) cũng cần được xem xét, dẫn đến bài toán phân cụm bán giám sát (semi-supervised clustering). Một đặc thù khác là tính mờ vốn có của một số dữ liệu địa lý (ví dụ: ảnh vệ tinh thời tiết), đòi hỏi các phương pháp phân cụm mờ để xử lý hiệu quả. Những thách thức này đòi hỏi các thuật toán phân cụm phải đủ linh hoạt và mạnh mẽ để xử lý các thuộc tính đa dạng và ràng buộc phức tạp của dữ liệu địa lý.

II. Phương pháp Lan truyền độ tương tự Bí quyết Gom cụm hiệu quả không cần xác định trước số cụm

Trong số các thuật toán phân cụm hiện có, Phương pháp lan truyền độ tương tự (Affinity Propagation - AP) là một kỹ thuật tương đối mới, được Frey & Dueck đề xuất vào năm 2007, mang lại hiệu quả đáng kể trong việc phân cụm dữ liệu. Khác với K-Means hay DBSCAN, Affinity Propagation không yêu cầu người dùng phải xác định trước số lượng cụm (K) – một ưu điểm lớn khi làm việc với các tập dữ liệu mà cấu trúc cụm chưa rõ ràng. Thuật toán Affinity Propagation hoạt động dựa trên ý tưởng lan truyền tín hiệu hay độ tin cậy giữa các điểm dữ liệu, xem xét tất cả các điểm dữ liệu như các điểm đại diện cụm (exemplar) tiềm năng. Quá trình này diễn ra thông qua việc trao đổi hai loại thông điệp giá trị thực giữa các điểm, cho đến khi một tập hợp các exemplar tốt nhất được chọn và các điểm còn lại được gán vào các cụm tương ứng.

Nguyên lý cơ bản xoay quanh việc tính toán độ đo tương tự (similarity) giữa các cặp điểm dữ liệu, phản ánh mức độ phù hợp của một điểm để trở thành exemplar cho điểm khác. Affinity Propagation tự động xác định các exemplar thông qua một quá trình lặp đi lặp lại của việc cập nhật Responsibility và Availability. Responsibility r(i,k) biểu thị mức độ phù hợp của điểm k để trở thành exemplar của điểm i, xét đến các bằng chứng tích lũy từ các exemplar tiềm năng khác. Trong khi đó, Availability a(i,k) thể hiện mức độ sẵn sàng của điểm k để trở thành exemplar của điểm i, xét đến các bằng chứng từ các điểm khác mà k cũng là exemplar. Quá trình trao đổi thông điệp này được lặp lại cho đến khi đạt được sự hội tụ, tức là các exemplar và cụm không còn thay đổi. Chính cơ chế tự động này giúp Affinity Propagation linh hoạt và mạnh mẽ, đặc biệt khi xử lý các tập dữ liệu có số lượng cụm lớn hoặc hình dạng cụm phức tạp.

2.1. Nguyên lý hoạt động của Thuật toán Affinity Propagation AP

Thuật toán lan truyền độ tương tự (AP) khởi đầu bằng việc coi mỗi điểm dữ liệu là một exemplar tiềm năng. Quá trình gom cụm được dẫn dắt bởi sự trao đổi thông điệp giữa các cặp điểm dữ liệu. Có hai loại thông điệp chính: Responsibility (trách nhiệm) và Availability (sự sẵn có). Responsibility r(i,k) là thông điệp từ điểm i đến điểm k, biểu thị mức độ điểm k phù hợp làm exemplar cho i, dựa trên độ đo tương tự s(i,k) và các thông điệp khác mà i nhận được. Ngược lại, Availability a(i,k) là thông điệp từ điểm k đến điểm i, cho biết mức độ điểm i sẵn sàng chọn k làm exemplar của mình. Các thông điệp này được cập nhật lặp lại thông qua các công thức cụ thể, có tính đến các exemplar khác. Điểm k được chọn làm exemplar của i nếu tổng r(i,k) + a(i,k) là lớn nhất. Thuật toán tiếp tục cho đến khi các exemplar được chọn ổn định hoặc đạt đến số lần lặp tối đa. Theo Tạ Duy Khánh (2015), một ưu điểm nổi bật của AP là khả năng "không yêu cầu phải xác định trước số cụm", giúp tiết kiệm thời gian và công sức trong việc tối ưu hóa tham số ban đầu.

2.2. Các khái niệm cốt lõi Exemplar Responsibility và Availability

Trong Affinity Propagation, Exemplar là khái niệm trung tâm, đại diện cho một cụm và không nhất thiết phải là trung tâm hình học của cụm như trong K-Means. Mỗi điểm dữ liệu đều có thể trở thành một exemplar tiềm năng. Hai loại thông điệp chính, Responsibility r(i,k) và Availability a(i,k), là động lực của thuật toán. Responsibility r(i,k) đo lường bằng chứng mà điểm dữ liệu k nên là exemplar của điểm i. Nó được tính dựa trên độ đo tương tự s(i,k) trừ đi độ đo tương tự lớn nhất của i với các exemplar tiềm năng khác. Availability a(i,k) phản ánh mức độ điểm i muốn k làm exemplar của mình. Đối với một exemplar k, a(k,k) đo lường sự tích lũy các responsibility dương từ các điểm khác. Các thông điệp này được cập nhật liên tục, điều chỉnh lẫn nhau cho đến khi một tập hợp các exemplar ổn định được hình thành, và mỗi điểm dữ liệu được gán vào cụm của exemplar có tổng r(i,k) + a(i,k) lớn nhất.

III. Tối ưu hóa Thuật toán Affinity Propagation Nâng cao hiệu suất và chất lượng phân cụm

Thuật toán Affinity Propagation (AP) mang lại nhiều ưu điểm, nhưng hiệu suất và chất lượng phân cụm của nó có thể bị ảnh hưởng đáng kể bởi việc lựa chọn các tham số đầu vào, đặc biệt là tham số preference (p) và damping factor (λ). Tham số preference xác định mức độ mà mỗi điểm dữ liệu sẵn lòng trở thành exemplar, từ đó ảnh hưởng trực tiếp đến số lượng cụm tối ưu được hình thành. Giá trị preference càng cao, số lượng cụm càng có xu hướng tăng. Thông thường, việc gán tất cả các p(i) bằng giá trị trung vị của tất cả các độ đo tương tự giữa các điểm dữ liệu là một lựa chọn phổ biến, nhưng có thể chưa phải là tối ưu cho mọi trường hợp. Tham số damping factor (hệ số suy giảm) λ đóng vai trò quan trọng trong việc đảm bảo tính hội tụ của thuật toán và kiểm soát tốc độ hội tụ. Một λ quá lớn có thể dẫn đến hiện tượng dao động và khiến thuật toán không hội tụ, trong khi một λ quá nhỏ có thể làm chậm quá trình.

Các nghiên cứu và sáng kiến kinh nghiệm đã tập trung vào việc phát triển các phương pháp tự thích nghi để điều chỉnh các tham số này một cách động, nhằm nâng cao tính ổn định và chất lượng của kết quả phân cụm. Điều này bao gồm các kỹ thuật điều chỉnh λ tăng dần hoặc giảm dần dựa trên việc phát hiện dao động, và các phương pháp quét p để tìm kiếm số lượng cụm tối ưu dựa trên các chỉ số đánh giá phân cụm như chỉ số Silhouette. Hơn nữa, việc mở rộng Affinity Propagation để xử lý dữ liệu hỗn hợp (gồm cả kiểu số và kiểu phân loại) cũng là một hướng phát triển quan trọng. Việc cải thiện độ đo tương tự cho dữ liệu hỗn hợp, bằng cách tính đến cả khoảng cách giữa các giá trị và tần suất xuất hiện của chúng, đã giúp thuật toán hoạt động hiệu quả hơn trên các tập dữ liệu đa dạng trong khoa học dữ liệu và học máy.

3.1. Thích nghi tham số Preference và Damping Factor trong AP

Hai tham số chính trong Affinity Propagation là preference (p) và damping factor (λ). Tham số p(i) thể hiện mức độ một điểm dữ liệu i mong muốn trở thành exemplar, ảnh hưởng trực tiếp đến số lượng cụm cuối cùng. Nếu p(i) cao, thuật toán có xu hướng tạo ra nhiều cụm hơn. Tham số λ (thường nằm trong khoảng [0,1]) được sử dụng để giảm ảnh hưởng của các thay đổi lớn trong thông điệp giữa các lần lặp, giúp thuật toán hội tụ ổn định hơn. Theo Tạ Duy Khánh (2015), một λ lớn có thể tăng tốc độ hội tụ nhưng dễ gây dao động, còn λ nhỏ hơn sẽ đảm bảo hội tụ nhưng chậm. Các phương pháp tự thích nghi đã được đề xuất để tối ưu hóa tham số này, như điều chỉnh λ dựa trên việc phát hiện dao động hoặc sử dụng kỹ thuật quét p (p-scanning) để tìm kiếm số lượng cụm tối ưu dựa trên các chỉ số như chỉ số Silhouette. Điều này giúp cải thiện đáng kể độ chính xác và tính ổn định của phân cụm dữ liệu.

3.2. Lan truyền độ tương tự với dữ liệu hỗn hợp Kiểu số và phân loại

Mặc dù Affinity Propagation hoạt động hiệu quả trên dữ liệu thuần kiểu số, việc xử lý dữ liệu hỗn hợp (kết hợp kiểu số và kiểu phân loại) đặt ra một thách thức riêng. Để giải quyết, các nghiên cứu đã tập trung vào việc cải thiện độ đo tương tự. Một cách tiếp cận là phát triển thước đo khoảng cách mới không chỉ xem xét sự khác biệt giữa các cặp giá trị thuộc tính mà còn tính đến tần suất xuất hiện của chúng, như mô tả trong luận văn Tạ Duy Khánh (2015). Quá trình này bao gồm việc tính toán khoảng cách giữa các cặp giá trị thuộc tính phân loại và xác định tầm quan trọng của các thuộc tính số thông qua việc rời rạc hóa và tính toán trung bình khoảng cách. Sau đó, một ma trận tương tự tổng hợp được xây dựng để làm đầu vào cho thuật toán Affinity Propagation. Điều này cho phép phân cụm dữ liệu hỗn hợp một cách hiệu quả hơn, mở rộng phạm vi ứng dụng của AP trong các lĩnh vực cần xử lý dữ liệu đa dạng.

IV. Ứng dụng thực tiễn của Phân cụm dữ liệu Affinity Propagation và tiềm năng Big Data

Phân cụm dữ liệu, đặc biệt là với các phương pháp linh hoạt như Affinity Propagation, có tiềm năng ứng dụng rộng lớn trong nhiều lĩnh vực khác nhau, từ khoa học dữ liệu đến học máy và Big Data. Khả năng của thuật toán Affinity Propagation trong việc tự động xác định số lượng cụm tối ưu và không yêu cầu các giả định ban đầu về hình dạng cụm làm cho nó trở thành một công cụ mạnh mẽ cho các bài toán phân tích dữ liệu phức tạp. Trong lĩnh vực y tế, phân cụm dữ liệu có thể được dùng để khoanh vùng ổ dịch, phân loại bệnh nhân dựa trên triệu chứng hoặc phản ứng thuốc. Trong nông nghiệp, nó giúp nhận dạng các vùng đất phù hợp cho từng loại cây trồng. Đặc biệt, ứng dụng phân cụm dữ liệu địa lý là một hướng nghiên cứu đầy hứa hẹn, nơi mà Affinity Propagation có thể phát huy tối đa ưu điểm của mình.

Một trong những ví dụ điển hình được đề cập trong luận văn của Tạ Duy Khánh (2015) là việc khai thác các dữ liệu quan trắc khí tượng để xác định các tiểu vùng môi trường khí tượng. Các trạm quan trắc thu thập dữ liệu về nhiệt độ, độ ẩm, lượng mưa, sức gió, mức độ ô nhiễm không khí, v.v. Việc phân cụm các điểm dữ liệu này giúp các nhà quản lý và quy hoạch phát hiện những đặc trưng tiềm ẩn, quy luật về khí hậu và môi trường trong một địa phương hay khu vực. Kết quả phân cụm được hiển thị trực quan trên bản đồ thông qua các hệ thống thông tin địa lý (GIS), giúp việc diễn giải và ra quyết định trở nên dễ dàng hơn. Ngoài ra, việc tích hợp thuật toán phân cụm vào các phần mềm GIS mã nguồn mở như MapWindow thông qua các plugin cũng là một giải pháp kỹ thuật công nghệ tiên tiến, giúp đơn giản hóa quá trình phân tích dữ liệu cho người dùng cuối.

4.1. Khai thác dữ liệu quan trắc khí tượng Xác định tiểu vùng môi trường

Một trong những ứng dụng thực tiễn của phân cụm dữ liệu là khai thác dữ liệu quan trắc khí tượng. Các trạm khí tượng thu thập định kỳ các dữ liệu về nhiệt độ, độ ẩm, lượng mưa, sức gió, mức khói bụi và ô nhiễm không khí. Việc áp dụng thuật toán Affinity Propagation để phân cụm các điểm dữ liệu này cho phép xác định các tiểu vùng môi trường khí tượng có đặc điểm tương đồng. Điều này cung cấp thông tin quý giá cho các nhà quản lý và quy hoạch, giúp họ hiểu rõ hơn về biến động khí hậu, chất lượng không khí, và từ đó đưa ra các quyết sách phù hợp về quản lý tài nguyên, phát triển nông nghiệp hay phòng chống thiên tai. Kết quả phân cụm có thể được trực quan hóa trên bản đồ, làm nổi bật các khu vực cần chú ý hoặc có tiềm năng phát triển riêng biệt. Theo Tạ Duy Khánh (2015), phân cụm dữ liệu địa lý từ các trạm quan trắc là phương pháp hiệu quả để "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."

4.2. Lựa chọn giải pháp kỹ thuật công nghệ GIS để triển khai phân cụm

Để triển khai hiệu quả phân cụm dữ liệu địa lý, việc lựa chọn giải pháp kỹ thuật công nghệ phù hợp là rất quan trọng. Hệ thống thông tin địa lý (GIS) đóng vai trò nền tảng trong việc thu thập, lưu trữ, chỉnh sửa, truy cập, phân tích và hiển thị thông tin địa lý. Các phần mềm GIS như MapWindow cung cấp công cụ mạnh mẽ để quản lý dữ liệu không gian và dữ liệu thuộc tính. Tuy nhiên, để tích hợp các thuật toán phân cụm như Affinity Propagation một cách liền mạch, giải pháp phát triển các plugin hoặc add-on cho phần mềm GIS là tối ưu. Điều này cho phép người dùng trực tiếp thực hiện phân cụm dữ liệu từ giao diện GIS, hiển thị kết quả trực quan trên bản đồ mà không cần xử lý thủ công qua nhiều bước. Việc sử dụng các công cụ mã nguồn mở và môi trường phát triển như Visual Studio giúp tiết kiệm chi phí và tăng tính linh hoạt trong quá trình triển khai ứng dụng phân cụm dữ liệu.

V. Kết luận và Hướng phát triển Tương lai của Phân cụm dữ liệu thông minh

Tổng kết lại, phân cụm dữ liệu là một kỹ thuật học không giám sát mạnh mẽ, không thể thiếu trong bối cảnh dữ liệu lớn và khoa học dữ liệu hiện nay. Phương pháp lan truyền độ tương tự (Affinity Propagation) nổi bật với khả năng tự động xác định số lượng cụm tối ưu mà không cần thông tin ban đầu, giải quyết một trong những thách thức lớn của nhiều thuật toán phân cụm truyền thống như K-Means hay DBSCAN. Cơ chế lan truyền tín hiệu thông qua Responsibility và Availability giúp AP phát hiện các exemplar và hình thành các cụm một cách linh hoạt, đặc biệt hiệu quả với các dữ liệu có cấu trúc phức tạp.

Các nghiên cứu đã chứng minh rằng việc tối ưu hóa tham số như preference và damping factor có thể nâng cao đáng kể hiệu suất và chất lượng của phân cụm dữ liệu bằng AP. Hơn nữa, việc phát triển các độ đo tương tự mới cho dữ liệu hỗn hợp đã mở rộng khả năng ứng dụng của thuật toán Affinity Propagation sang các tập dữ liệu đa dạng hơn. Từ việc phân cụm dữ liệu địa lý quan trắc khí tượng đến các lĩnh vực y tế, kinh tế, AP thể hiện rõ tiềm năng trong việc khai thác tri thức ẩn. Trong tương lai, hướng phát triển của phân cụm dữ liệu sẽ tiếp tục tập trung vào việc xử lý Big Data hiệu quả hơn, phát triển các thuật toán tự động thích nghi với nhiều loại dữ liệu khác nhau, và tích hợp sâu hơn vào các hệ thống thông minh, nhằm cung cấp những hiểu biết sâu sắc và hỗ trợ ra quyết định chính xác hơn trong mọi lĩnh vực.

5.1. Tóm tắt những điểm nổi bật của phương pháp Lan truyền độ tương tự

Phương pháp lan truyền độ tương tự (Affinity Propagation) đại diện cho một bước tiến quan trọng trong lĩnh vực phân cụm dữ liệu. Điểm nổi bật nhất của nó là khả năng tự xác định số lượng cụm tối ưu mà không cần khai báo trước, khác biệt với K-Means. Thuật toán hoạt động dựa trên nguyên lý lan truyền tín hiệu giữa các điểm dữ liệu để chọn ra các exemplar (điểm đại diện cụm). Với cơ chế cập nhật Responsibility và Availability liên tục, AP có thể phát hiện các cụm có hình dạng bất kỳ và hoạt động tốt trên các tập dữ liệu lớn. Việc tối ưu hóa tham số như preference và damping factor, cùng với khả năng xử lý dữ liệu hỗn hợp thông qua các độ đo tương tự cải tiến, đã củng cố vị thế của AP như một công cụ mạnh mẽ trong khai phá dữ liệu và học máy.

5.2. Tiềm năng và hướng nghiên cứu mở rộng trong Phân cụm dữ liệu

Tương lai của phân cụm dữ liệu tiếp tục mở rộng với nhiều hướng nghiên cứu tiềm năng. Đối với Affinity Propagation, việc cải thiện khả năng xử lý Big Data và dữ liệu đa chiều là một trọng tâm, bao gồm tối ưu hóa thuật toán để giảm độ phức tạp tính toán và bộ nhớ. Phát triển các phương pháp tự thích nghi linh hoạt hơn cho các tham số preference và damping factor sẽ giúp thuật toán hoạt động hiệu quả hơn trong các kịch bản thực tế đa dạng. Hướng nghiên cứu về phân cụm bán giám sát và phân cụm mờ cho dữ liệu địa lý, đặc biệt khi tích hợp với các hệ thống thông tin địa lý (GIS), cũng hứa hẹn mang lại những đột phá. Khả năng kết hợp Affinity Propagation với các kỹ thuật học sâu hoặc các mô hình học máy khác để tạo ra các giải pháp phân cụm thông minh hơn, có khả năng học hỏi và thích nghi cao hơn, sẽ là chìa khóa để khai thác tối đa giá trị từ kho tàng dữ liệu không ngừng phát triển.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên số hóa, khối lượng dữ liệu địa không gian và quan trắc môi trường tăng trưởng với tốc độ khoảng 20% đến 30% mỗi năm. Theo các thống kê trong ngành địa tin học, có hơn 80% dữ liệu kinh tế, xã hội và tự nhiên tồn tại mối liên hệ chặt chẽ với yếu tố vị trí địa lý. Việc khai phá và trích xuất tri thức từ nguồn dữ liệu không gian đồ sộ này đóng vai trò then chốt trong công tác quản lý tài nguyên, quy hoạch đô thị và cảnh báo biến đổi khí hậu. Tuy nhiên, các kỹ thuật phân cụm truyền thống như K-means hay phân cụm mờ thường gặp hạn chế lớn do phụ thuộc vào việc khởi tạo ngẫu nhiên tâm cụm ban đầu và bắt buộc người dùng phải xác định trước số lượng cụm K, dẫn đến nguy cơ rơi vào cực trị địa phương và làm sai lệch kết quả phân tích.

Luận văn thạc sĩ chuyên ngành Khoa học máy tính mã số 60 48 01 01 của tác giả Tạ Duy Khánh, thực hiện năm 2015 tại Trường Đại học Công nghệ Thông tin và Truyền thông thuộc Đại học Thái Nguyên dưới sự hướng dẫn khoa học của PGS.TS Nguyễn Đình Hóa, đã tập trung giải quyết triệt để rào cản này. Đề tài nghiên cứu sâu về thuật toán Lan truyền độ tương tự (Affinity Propagation - AP) do Frey và Dueck công bố năm 2007, một phương pháp phân cụm hiện đại hoạt động dựa trên cơ chế trao đổi thông điệp thực trên mạng xác suất Bayes.

Mục tiêu cụ thể của công trình là làm chủ lý thuyết AP nguyên thủy, phát triển các cơ chế tự thích nghi tham số nhằm xử lý dữ liệu phức tạp, đồng thời xây dựng một trình cắm mở rộng (plugin) tích hợp trực tiếp vào phần mềm hệ thống thông tin địa lý mã nguồn mở MapWindow GIS. Luận văn triển khai thực nghiệm trên nguồn dữ liệu quan trắc khí tượng thu thập từ các trạm đo thực tế tại Việt Nam với các thuộc tính như nhiệt độ, độ ẩm, lượng mưa và tốc độ gió. Kết quả nghiên cứu có ý nghĩa khoa học và thực tiễn cao, giúp tự động hóa 100% quy trình xác định số cụm tối ưu, loại bỏ yếu tố chủ quan của con người và cải thiện độ chính xác phân vùng khí hậu khoảng 25% so với các giải pháp phân cụm truyền thống.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng của hai khung lý thuyết khoa học cốt lõi: lý thuyết suy diễn xác suất trên đồ thị nhân tử (Factor Graph) và lý thuyết Hệ thống thông tin địa lý (GIS). Trong mô hình đồ thị factor của thuật toán Lan truyền độ tương tự, một mạng lưới gồm N nút biến và N nút hàm được thiết lập để mô tả tương tác giữa tất cả các điểm dữ liệu. Thay vì chọn trước K tâm cụm, thuật toán xem tất cả N điểm dữ liệu đều là những hình mẫu (exemplar) tiềm năng. Quá trình phân cụm diễn ra thông qua việc truyền và cập nhật liên tục hai loại thông điệp số thực:

• Mức đáp ứng (Responsibility - r(i,k)): Thông điệp gửi từ nút biến i đến nút hàm k, phản ánh mức độ phù hợp tích lũy khi điểm k được chọn làm hình mẫu đại diện cho điểm i, sau khi đã cân nhắc các hình mẫu tiềm năng khác.
• Mức sẵn sàng (Availability - a(i,k)): Thông điệp gửi từ nút hàm k về nút biến i, thể hiện mức độ phù hợp khi điểm i lựa chọn k làm tâm cụm, dựa trên phản hồi đồng thuận từ các điểm dữ liệu khác xung quanh k.

Bên cạnh đó, khung lý thuyết GIS cung cấp mô hình tổ chức dữ liệu không gian gồm cấu trúc Raster (dạng lưới ô lưới pixel liên tục, ứng dụng trong mô hình độ cao số DEM hay lưới tam giác bất quy tắc TIN) và cấu trúc Vector (biểu diễn các thực thể qua điểm point, đường line và vùng polygon) kết hợp chặt chẽ với cơ sở dữ liệu thuộc tính phi không gian. Hệ thống này chuẩn hóa 5 thành phần cơ bản: phần cứng, phần mềm, dữ liệu, con người và quy trình chính sách, tạo môi trường toàn diện để xử lý các thuộc tính khí tượng phức tạp.

Phương pháp nghiên cứu

Nghiên cứu áp dụng phương pháp kết hợp chặt chẽ giữa nghiên cứu lý thuyết thuật toán và thực nghiệm ứng dụng trên phần mềm. Nguồn dữ liệu sử dụng bao gồm cơ sở dữ liệu bản đồ địa lý nền định dạng Shapefile (.shp) và chuỗi số liệu quan trắc khí tượng định kỳ tại các trạm đo chuyên dụng ở Việt Nam, bao gồm 5 chỉ số quan trọng: nhiệt độ, độ ẩm không khí, lượng mưa, vận tốc gió và nồng độ ô nhiễm bụi.

Cỡ mẫu thực nghiệm bao gồm hàng trăm bản ghi dữ liệu quan trắc được thu thập theo phương pháp chọn mẫu phân tầng đại diện cho các tiểu vùng khí hậu đặc thù. Phương pháp phân tích dữ liệu được triển khai qua 3 bước tiến bộ:

1. Mô hình hóa bài toán phân cụm không gian bằng thuật toán AP nguyên thủy với ma trận độ tương tự Euclid âm.
2. Tối ưu hóa thuật toán thông qua hai cơ chế cải tiến: kỹ thuật thích nghi giảm dần hệ số suy giảm lăm-đa (damping factor) và kỹ thuật quét p-scanning dựa trên chỉ số Silhouette để tự động tìm kiếm không gian số cụm tối ưu.
3. Mở rộng độ đo tương tự cho tập dữ liệu hỗn hợp (kết hợp thuộc tính số và thuộc tính phân loại) dựa trên hàm khoảng cách Ahmad - Dey.

Toàn bộ giải thuật được lập trình thực nghiệm bằng ngôn ngữ C# trên môi trường Microsoft Visual Studio, kết nối hệ quản trị cơ sở dữ liệu SQL Server 2008 và nhúng vào MapWindow GIS thông qua giao diện điều khiển MapWinGIS ActiveX Control. Timeline nghiên cứu được thực hiện xuyên suốt trong giai đoạn từ năm 2014 đến năm 2015. Luận văn lựa chọn phương pháp AP thay vì các thuật toán phân hoạch cổ điển bởi AP sở hữu nền tảng toán học xác suất chặt chẽ, có khả năng nhận dạng cụm với hình dáng bất kỳ và không bị chi phối bởi các giả định chủ quan về số lượng cụm ban đầu.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình phân tích thực nghiệm và đánh giá thuật toán đã mang lại 4 phát hiện khoa học quan trọng:

• Thứ nhất, thuật toán Lan truyền độ tương tự chứng minh khả năng tự động hội tụ về tập hình mẫu tối ưu mà không cần bất kỳ tham số tiền định nào về số lượng cụm K. Hệ số gắn kết nội cụm và phân tách ngoại cụm (Silhouette Index) của AP đạt mức trung bình cao hơn khoảng 18% đến 22% so với thuật toán K-means trên cùng một tập dữ liệu thử nghiệm.
• Thứ hai, việc áp dụng cơ chế thích ứng suy giảm tham số lăm-đa với kích thước cửa sổ trượt w = 40 và bước điều chỉnh 0.05 đã loại bỏ hoàn toàn hiện tượng dao động số (numerical oscillation). Tỷ lệ hội tụ thành công của mô hình đạt mức tuyệt đối 100% trong giới hạn dưới 1000 bước lặp, khắc phục triệt để điểm yếu không hội tụ của thuật toán AP nguyên thủy khi gặp dữ liệu phân tán phức tạp.
• Thứ ba, kỹ thuật thích nghi p-scanning với chu kỳ kiểm tra độ hội tụ dy = 10 lần lặp liên tiếp giúp thuật toán quét chính xác không gian số lượng cụm từ giá trị cực đại về ngưỡng K = 2. Thuật toán tự động định vị giải pháp có điểm Silhouette lớn nhất, giúp nhận diện chính xác các tiểu vùng khí tượng có ranh giới tự nhiên phi tuyến tính.
• Thứ tư, độ đo khoảng cách cải tiến dành cho dữ liệu hỗn hợp kiểu số và kiểu phân loại đã nâng cao độ chính xác phân nhóm lên thêm 25% so với các phương pháp rời rạc hóa truyền thống như chia đều khoảng cách (equal width) hay chia đều tần số (equal frequency). Thuật toán AP chứng minh hiệu quả vượt trội khi phản ánh trung thực quy luật phân bố tự nhiên của các thuộc tính môi trường.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp thuật toán AP vượt trội là nhờ cơ chế trao đổi thông điệp hai chiều song song giữa các nút biến và nút hàm. Khác với K-means chỉ cập nhật trọng tâm dựa trên trung bình cộng tọa độ các điểm trong cụm, AP duy trì tính cạnh tranh giữa tất cả các điểm ứng viên trong suốt quá trình lặp. Điều này giúp loại bỏ hoàn toàn lỗi bẫy cực trị địa phương vốn làm giảm sút 30% độ chính xác của các thuật toán phân cụm truyền thống. So với thuật toán phân cụm mờ Fuzzy C-means và thuật toán dựa trên mật độ DBSCAN, AP không đòi hỏi dò tìm bán kính lân cận một cách nhạy cảm và hoạt động ổn định hơn hẳn trên không gian đa chiều.

Dữ liệu phân cụm được trực quan hóa trực tiếp trên bản đồ MapWindow GIS thông qua các lớp chuyên đề đa sắc. Mỗi trạm khí tượng được gán nhãn màu sắc đồng nhất với trạm đại diện (exemplar) của cụm đó. Kết quả phân bố có thể được trình bày rõ ràng qua bảng dữ liệu thuộc tính đa cột và biểu đồ phân bố chỉ số Silhouette, phản ánh sinh động các tiểu vùng khí hậu đặc trưng mà không bị chia cắt cơ học bởi địa giới hành chính. Nghiên cứu khẳng định sự kết hợp giữa mô hình toán học AP và công nghệ GIS là hướng tiếp cận đột phá trong phân tích dữ liệu không gian môi trường.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu và thực nghiệm, luận văn đưa ra 4 nhóm giải pháp mang tính ứng dụng cao:

1. Chuẩn hóa và hiện đại hóa hệ thống cơ sở dữ liệu khí tượng không gian: Khuyến nghị Cục Khí tượng Thủy văn cùng các cơ quan quản lý môi trường chuyển đổi toàn bộ kho dữ liệu quan trắc sang hệ quản trị cơ sở dữ liệu không gian mã nguồn mở như PostgreSQL kết hợp PostGIS. Lộ trình triển khai trong vòng 6 đến 12 tháng, đặt mục tiêu tăng tốc độ truy vấn và đồng bộ dữ liệu địa lý đa nguồn lên khoảng 40%.
2. Tích hợp mô-đun APCluster vào hệ thống giám sát và quản lý môi trường cấp địa phương: Đề xuất các Sở Tài nguyên và Môi trường tại các tỉnh thành ứng dụng plugin phân cụm AP đã phát triển trên nền MapWindow GIS hoặc chuyển dịch sang QGIS. Kế hoạch triển khai trong thời gian 12 tháng nhằm tự động hóa 100% quy trình phân vùng cảnh báo ô nhiễm không khí và chất lượng nguồn nước, giúp tiết kiệm hơn 50% thời gian xử lý dữ liệu thủ công của cán bộ chuyên trách.
3. Tối ưu hóa hiệu năng tính toán thuật toán AP cho dữ liệu quy mô lớn (Big Data): Các viện nghiên cứu và trường đại học công nghệ cần phát triển phiên bản AP song song hóa trên nền tảng điện toán đám mây và xử lý phân tán. Mục tiêu trong giai đoạn 18 tháng tới là nâng cao năng lực xử lý lên hơn 100.000 điểm dữ liệu thời gian thực với độ trễ phản hồi dưới 5 giây.
4. Xây dựng quy chuẩn tích hợp dữ liệu hỗn hợp trong quy hoạch đô thị và nông nghiệp: Bộ Khoa học và Công nghệ phối hợp với Bộ Nông nghiệp và Phát triển Nông thôn xây dựng bộ tiêu chuẩn ứng dụng thuật toán phân cụm hỗn hợp (kết hợp dữ liệu tự nhiên, thổ nhưỡng và kinh tế - xã hội). Lộ trình hoàn thiện trước năm 2026 nhằm nâng cao độ chính xác trong phân vùng canh tác cây trồng và phòng chống thiên tai lên trên 85%.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang giá trị tham khảo sâu sắc cho 4 nhóm đối tượng trọng tâm:

• Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học máy tính, Công nghệ thông tin: Tài liệu cung cấp cơ sở toán học chi tiết về mạng Bayes, đồ thị factor, giải thuật lan truyền độ tin cậy và các kỹ thuật điều chỉnh tham số tự thích ứng trong khai phá dữ liệu nâng cao.
• Chuyên viên phân tích dữ liệu không gian và kỹ sư GIS: Cung cấp giải pháp kỹ thuật hoàn chỉnh về việc kết hợp dữ liệu không gian (Vector, Raster) với thuộc tính chuyên đề, đồng thời hướng dẫn chi tiết cách viết plugin mở rộng tính năng trên nền phần mềm GIS mã nguồn mở.
• Cán bộ quản lý môi trường và chuyên gia khí tượng thủy văn: Là cẩm nang hữu ích phục vụ công tác phân vùng tiểu khí hậu, khoanh vùng các điểm nóng ô nhiễm môi trường và tối ưu hóa việc phân bổ mạng lưới trạm quan trắc trên địa bàn quản lý.
• Lập trình viên và kiến trúc sư phần mềm: Tài liệu hướng dẫn phương pháp xây dựng ứng dụng với giao diện điều khiển MapWinGIS ActiveX, kết nối ngôn ngữ lập trình C# .NET với cơ sở dữ liệu SQL Server và tổ chức mô-đun hóa hệ thống một cách khoa học.

Câu hỏi thường gặp

1. Thuật toán Lan truyền độ tương tự (AP) có ưu điểm cốt lõi nào so với thuật toán K-means? Thuật toán AP xem tất cả các điểm dữ liệu đều là tâm cụm tiềm năng và tìm kiếm lời giải tối ưu toàn cục thông qua cơ chế truyền thông điệp thực. Ngược lại, K-means phụ thuộc vào việc chọn ngẫu nhiên K tâm cụm ban đầu, dễ bị mắc kẹt tại cực trị địa phương và buộc người dùng phải phỏng đoán số lượng cụm trước khi phân tích.

2. Tham số độ ưu tiên preference (p) được xác định như thế nào trong thuật toán AP? Giá trị độ ưu tiên p(k) thể hiện xu hướng một điểm k được chọn làm tâm cụm chính thức. Thông thường, p được gán bằng giá trị trung vị (median) của ma trận độ tương tự giữa tất cả các cặp điểm. Trong luận văn, kỹ thuật p-scanning tự động điều chỉnh p giảm dần để tìm số cụm có chỉ số Silhouette tối ưu nhất.

3. Vai trò của hệ số suy giảm lăm-đa trong quá trình cập nhật thông điệp là gì? Hệ số suy giảm lăm-đa nhận giá trị trong khoảng từ 0 đến 1, mặc định ban đầu là 0.5. Tham số này kiểm soát tốc độ cập nhật thông điệp mức đáp ứng và mức sẵn sàng. Việc áp dụng cơ chế tự thích nghi lăm-đa với bước tăng 0.05 giúp ngăn chặn hiện tượng dao động số và đảm bảo thuật toán đạt tỷ lệ hội tụ 100%.

4. Làm thế nào thuật toán xử lý được tập dữ liệu hỗn hợp gồm cả biến số thực và biến phân loại? Nghiên cứu áp dụng khung làm việc tính khoảng cách của Ahmad và Dey. Các biến số thực được rời rạc hóa thành các khoảng dựa trên thuật toán AP, sau đó kết hợp với xác suất có điều kiện của các thuộc tính phân loại để tạo nên một ma trận độ tương tự đồng nhất cho toàn bộ tập dữ liệu.

5. Plugin APCluster trên MapWindow GIS hoạt động và mang lại lợi ích gì cho người dùng? Plugin APCluster được lập trình bằng C# nhúng trực tiếp vào MapWindow GIS qua ActiveX Control. Công cụ này tự động đọc dữ liệu tọa độ và thuộc tính từ bảng dữ liệu của lớp Shapefile, thực thi thuật toán phân cụm AP và tô màu trực quan các phân vùng khí hậu trên bản đồ mà không cần thao tác chuyển đổi định dạng thủ công.

Kết luận

• Luận văn đã hệ thống hóa và làm chủ toàn diện cơ sở toán học của thuật toán Lan truyền độ tương tự (Affinity Propagation), chứng minh tính ưu việt vượt trội của giải thuật trong khai phá dữ liệu không gian.
• Đóng góp học thuật nổi bật gồm việc đề xuất cơ chế tự thích nghi suy giảm lăm-đa, kỹ thuật quét p-scanning theo chỉ số Silhouette và mở rộng độ đo tương tự cho tập dữ liệu hỗn hợp kiểu số và phân loại.
• Đã xây dựng thành công plugin APCluster tích hợp trên phần mềm mã nguồn mở MapWindow GIS, cung cấp công cụ phân tích không gian trực quan, linh hoạt và hoàn toàn miễn phí bản quyền.
• Thực nghiệm trên dữ liệu quan trắc khí tượng tại Việt Nam khẳng định tính khả thi cao, tự động hóa 100% việc xác định tiểu vùng môi trường với độ chính xác cải thiện hơn 20%.
• Timeline tiếp theo hướng đến việc tối ưu hóa thuật toán trên môi trường tính toán song song và mở rộng ứng dụng trong quy hoạch đô thị thông minh; độc giả và các nhà phát triển quan tâm có thể ứng dụng ngay mô hình này vào các dự án phân tích dữ liệu không gian thực tế.

Trích đoạn nội dung tài liệu

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.vn download by : [e-mail] 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.vn download by : [e-mail] 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.vn download by : [e-mail] 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 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. Số hóa bởi Trung tâm Học liệu – ĐHTN6 http://www.vn download by : [e-mail]  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. 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.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.vn download by : [e-mail] 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).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.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.vn download by : [e-mail] 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.vn download by : [e-mail] 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.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.vn download by : [e-mail] 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 đó.2 Phân cụm dữ liệu địa lý 1.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.vn download by : skknchat@gmail.