Luận văn thạc sĩ 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ĩ 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.

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.