Chương 1: Tổng quan. Khái quát về phương pháp phân cụm dữ liệu dựa trên GIS và khảo sát các nghiên cứu có liên quan, nêu mục tiêu, nội dung luận văn và ý nghĩa thực tiễn của luận văn. 15 Chương 2: Cơ sở lý thuyết. Trình bày lý thuyết về các thuật toán DBSCAN, HDBSCAN, mạng chú ý đồ thị (GAT), chỉ số thông tin lẫn nhau được chuẩn hóa NMI, phương pháp tối ưu hóa Adam và mô hình đề xuất CP2 Vec.
Chương 3: Phương pháp thực hiện. Trình bày phương pháp xây dựng đồ thị dựa trên vi trí địa lí. Trình bày về học biéu điễn đồ thị dựa trên vị trí nhận biết cộng đồng thông qua GAT bằng phương pháp phát hiện cộng đồng Louvain. Chương 4: Thực nghiệm.
Mô tả bộ dữ liệu và cài đặt thực nghiệm. Thảo luận kết quả thực nghiệm. Ngoài ra, dựa trên kết quả thực nghiệm, nghiên cứu cắt bỏ các siêu tham số trong mô hình. Chương 5: Kết luận và hướng phát triển.
Tổng kết lại những kết quả đã đạt được trong nghiên cứu, trình bày những mặt còn tồn tại của bài toán, cũng như trình bày hướng nghiên cứu và phát triển trong tương lai. CƠ SỞ LÝ THUYET Tóm tắt: Chương hai sẽ trình bày lý thuyết chính liên quan bài toán gom cụm dữ liệu dựa trên GIS và mô hình dé xuất CP2Vec. Bao gồm các trình bày sơ nét về thuật toán DBSCAN, HDSCAN và mạng nơ-ron đồ thị (GNN) và mạng GNN có tích hop cơ chế chú ÿ (attention) (GAT). Thuật toán DBSCAN 2.
Khái niệm Thuật toán DBSCAN (Density Based Spatial Clustering of Applications with Noise) do Martin Ester và các tác giả khác đề xuất vào năm 1996. Trong thuật toán này, ý tưởng chính là đối với một tập hợp các điểm trong không gian cho trước, các điểm có nhiều hàng xóm trong một bán kính có định sẽ được nhóm thành một cụm. Các điểm đánh dấu là ngoại lệ nếu chúng được tách ra khỏi các điểm trong cụm, chúng thuộc về các vùng có mật độ thấp. Các định nghĩa trong thuật toán DBSCAN Định nghĩa 1: Một điểm dữ liệu được coi là thuộc về một cụm nếu có đủ số lượng các điểm khác trong khoảng cách không quá e từ nó (bao gồm chính nó) và nó phải là một điểm lõi (core point) - có ít nhất minpts điểm khác trong khoảng cách e.
Nếu một điểm không được xác định là điểm lõi và không thuộc bất kỳ cụm nào, nó sẽ được coi là một điểm nhiễu (noise point). Công thức mô tả cho Định nghĩa 1 của DBSCAN: Nếu d(P,Q) < z, thì Q được coi là một điểm láng giềng của P. Nếu số lượng điểm láng giềng của P lớn hơn hoặc bằng minpts, P được coi là một điểm lõi (core point). Một điểm dữ liệu được coi là thuộc về một cụm nếu nó là một điểm lõi hoặc nằm trong bán kính e của một điểm lõi khác.
Các điểm dit liệu còn lại được coi là điểm nhiễu (noise points). 17 Trong đó: d(P, Q) là khoảng cách giữa hai điểm dữ liệu P và Q và minpts là số lượng tối thiểu các điểm khác trong khoảng cách e để một điểm dữ liệu được coi là một điểm lõi. Định nghĩa 2: Khả năng tiếp cận trực tiếp mật độ được sử dụng nhằm xác định các điểm thuộc về cùng một cụm. Một điểm được đánh giá là có khả năng tiếp cận trực tiếp mật độ nếu nó nằm trong bán kính e của các điểm khác.
Dé xác định xem một điểm có khả năng tiếp cận trực tiếp mật độ hay không, thuật toán sẽ kiểm tra xem có đủ số lượng điểm khác trong bán kính e của nó hay không. Nếu số lượng điểm đó đạt đủ ngưỡng được định trước, điểm đó sẽ được xem là có khả năng tiếp cận trực tiếp mật độ và sẽ được thêm vào cùng một cụm với các điểm khác trong bán kính e. Điều này giúp cho thuật toán DBSCAN phân loại các điểm dữ liệu thành các cụm có hình dạng và kích thước khác nhau mà không cần biết trước số lượng cụm và khoảng cách giữa các điểm. Theo định nghĩa, điểm A được coi là có thể tiếp cận trực tiếp mật độ của điểm B néu: + Điểm A và điểm B đều thuộc cùng một cụm.
+ Mật độ của điểm B cao hơn hoặc bằng mật độ của điểm A. + Khoảng cách giữa các điểm là nhỏ hơn hoặc bằng e (epsilon). Khi hai điểm A và B được xác định là có thể tiếp cận trực tiếp mật độ của nhau, chúng được coi là liên kết chặt chẽ và sẽ được quy hoạch vào cùng một cụm trong quá trình phân cụm của DBSCAN. Khả năng tiếp cận trực tiếp mật độ là một trong nhiều yếu tố quan trọng giúp kỹ thuật DBSCAN phân cụm các điểm dữ liệu theo các cụm dày đặc, đồng thời loại bỏ các điểm nhiễu (noise points) không thuộc vào bất kỳ cụm nào.
Định nghĩa 3: Khả năng tiếp cận mật độ (density-reachable) đề cập đến khả năng kết nối các điểm thành một cụm dựa trên mật độ của chúng. Theo đó, một điểm P được coi là tiếp cận mật độ từ một điểm Q trong cùng một cụm nếu có một chuỗi liên kết các điểm từ Q đến P sao cho mật độ của cụm không bị đứt đoạn theo chuỗi đó. Điều này 18 đảm bảo rằng các điểm cùng cụm sẽ có khả năng kết nối cao dựa trên mật độ của chúng, và các cụm khác nhau sẽ được phân biệt dựa trên khoảng cách và mật độ. Như vậy, các điểm tiếp cận mật độ thường được gom lại trong cùng một cụm với nhau.
Khả năng tiếp cận mật độ được sử dụng để phân loại các điểm dữ liệu vào các cụm tương đồng nhau, dựa trên sự gần gũi và liên kết về mật độ giữa chúng. Ví dụ ta có bộ dữ liệu về những người học tập trong một trường học và ta muốn phân nhóm những người này dựa trên mức độ hoạt động của họ trên mạng xã hội. Tuy nhiên, một số người không sử dụng mạng xã hội hoặc không chia sẻ nhiều thông tin cá nhân, dẫn đến việc không thể đánh giá mức độ hoạt động trên mạng. Trong trường hợp trên, các cá nhân này sẽ không được xem là tiếp cận được từ các cá nhân khác và thông tin trên mạng, nên sự tồn tại của các nhóm dữ liệu được phân biệt bởi mật độ dữ liệu.
Do đó, ta có thé sử dụng thuật toán DBSCAN để phát hiện những điểm này và xóa chúng khỏi dữ liệu hoặc đặt chúng vào một nhóm khác. Phân loại điểm trong DBSCAN Trong DBSCAN, các điểm được phân loại thành ba loại khác nhau: Điểm lõi (core point), điểm biên (border point) và điểm nhiễu (noise point). Các loại điểm này được định nghĩa dựa trên mật độ các điểm của các vùng xung quanh chúng. Hình đưới mô tả chỉ tiết cả ba loại điểm trên.
e@ Noise point (Outlier) Hinh 2. Hinh minh hoa 3 loai diém trong thuật toán DBSCAN. Nguồn: https://www.com/blog/dbscan-python. + Điểm biên (border point): Là các điểm trong không gian dữ liệu mà không phải là điểm lõi nhưng nằm trong bán kính e của một điểm lõi.
+ Điểm nhiễu (noise point) là những điểm trong không gian dữ liệu mà không phải là điểm lõi và không thuộc vào bat kỳ cụm nao. Trong thuật toán DBSCAN, có hai tham số được dùng dé điều chỉnh quá trình gom cụm: + Epsilon (e): Tham số này xác định bán kính của một vùng xung quanh mỗi điểm dữ liệu. Nếu có ít nhất minpis điểm trong vùng này (bao gồm chính điểm đó), thì điểm đó được coi là một điểm lõi và sẽ được gán vào một cụm. Tham số này cũng được gọi là bán kính phân cách.
+ min,rs: Tham số này xác định số lượng điểm tối thiểu trong một vùng lân cận của một điểm lõi để được coi là một cụm. Nếu không đủ số lượng điểm này trong khu vực lân cận, điểm đó sẽ được coi là nhiễu và không thuộc vào bat kỳ cụm nào. Phụ thuộc từng bộ dữ liệu cụ thể và mục đích sử dụng, các giá tri của £ và minsts có thể được điều chỉnh dé đạt được kết quả gom cụm tốt hơn. Khi xem xét một cặp điểm bat kỳ (P, Q), có ba trường hợp chính có thé xảy ra: + Cặp điểm (P, Q) thuộc cùng một cụm dữ liệu: Nếu cả hai điểm P và Q đều liên kết với nhau thông qua các điểm khác trong cụm dữ liệu, tức là khoảng cách giữa chúng nhỏ hơn hoặc bằng một giá trị ngưỡng được xác định trước (thường được gọi là €), thi P và Q thuộc cùng một cụm dữ liệu.
+ Cặp điểm (P, Q) không thuộc bắt kỳ cụm dữ liệu nào: Nếu cả hai điểm P và Q đều không liên kết với bat kỳ điểm nào trong dữ liệu, tức là không có điểm nao nằm trong khoảng cách e từ cả P và Q, thì P và Q được coi là điểm nhiễu (noise) hoặc ngoại lệ (outlier) và không thuộc bất cứ cụm đữ liệu nào. + Cặp điểm (P, Q) có một điểm thuộc cụm dữ liệu và một điểm là điểm nhiễu: Trường hợp này xảy ra khi một trong hai điểm P hoặc Q thuộc một cụm dữ liệu trong 20 khi điểm còn lại là điểm nhiễu. Như vậy, điểm nhiễu không được xem là một thành viên của cụm dữ liệu, và điểm thuộc cụm dữ liệu sẽ không được kết nối với điểm nhiễu. Như vậy, điều quan trọng trong DBSCAN là quyết định xem một điểm có kết nối với một cụm dữ liệu nào đó hay không, dựa trên hai tham số là bán kính € và số lượng điểm kế thừa minpts.
Thông qua việc kiểm tra khoảng cách và số lượng điểm trong khoảng cách đó, ta có thé xác định liệu cặp điểm (P, Q) có thuộc cùng một cụm dir liệu hay không. Các bước trong thuật toán DBSCAN “Thuật toán sẽ bắt đầu từ một điểm bat ky và lan rộng dan ra dé mở rộng thêm phạm vi của cụm. Khi đạt tới những điểm biên của cụm hiện tại, DBSCAN sẽ tạo ra một cụm mới và tiếp tục các bước tương tự cho cụm mới đó. Cụm sẽ được mở rộng cho đến khi không còn điểm nào ở biên của nó.
O ve: "»@ ‹ CSC fe Tile OYlào GOO OF ORO "® @-OFC O OQ ner, le Hình 2. Quá trình lan truyền dé xác định các cụm thuật toán DBSCAN Nguồn: https://ml-explained.com/blog/dbscan-explained 21 Các bước thực hiện của DBSCAN: + Bước | (Khởi tạo): Chọn một điểm dữ liệu ngẫu nhiên chưa được gan cụm. Xác định các tham số quan trọng cho thuật toán, bao gồm khoảng cách epsilon (e) và số lượng điểm tối thiểu trong một vùng kề (minnr;).