Ma trận tiệm cận m x m cho m điểm dữ liệu có thể được định nghĩa là một đồ thị dày đặc, trong đó mỗi nút được liên kết với một số nút khác và trọng số của cạnh giữa một số nhóm nút theo độ gần nhau của chúng. Mặc dù mỗi đối tượng có một số phương thức tương tự với từng đối tượng khác, nhưng đối với hầu hết các tập dữ liệu, các đối tượng rất giống nhau đối với một số ít đối tượng và giống nhau yếu đối với hầu hết các đối tượng khác.
Tính năng này có thể được sử dụng để chia nhỏ đồ thị tiệm cận (ma trận), bằng cách đặt một số giá trị có độ tương đồng thấp (độ phân tán cao) thành 0 trước khi bắt đầu quá trình phân nhóm thực tế. Ví dụ, có thể thực hiện phân biệt bằng cách chia tất cả các liên kết có cùng (không giống nhau) bên dưới (ở trên) một ngưỡng xác định hoặc bằng cách chỉ duy trì các liên kết đến k lân cận gần nhất của điểm. Phương pháp này tạo ra cái được gọi là đồ thị láng giềng gần nhất.
Các lợi ích của việc thưa thớt như sau -
Kích thước dữ liệu được giảm xuống - Lượng dữ liệu cần được xử lý để phân cụm dữ liệu cực kỳ giảm. Việc phân biệt có thể loại bỏ hơn 99% các mục nhập trong ma trận gần nhau. Do đó, quy mô của các vấn đề có thể được quản lý được nâng cao.
Tính năng phân nhóm có thể hoạt động tốt hơn - Các phương pháp Sparsification giữ liên kết đến các đối tượng láng giềng gần nhất của chúng trong khi phân chia các kết nối đến các đối tượng khác biệt hơn. Điều này nhằm duy trì với nguyên tắc láng giềng gần nhất rằng những láng giềng gần nhất của một đối tượng có ảnh hưởng thuộc về lớp (cụm) tương tự như chính đối tượng đó. Điều này làm giảm tác động của tiếng ồn và các yếu tố ngoại lai và tạo ra sự khác biệt giữa các cụm.
Có thể sử dụng các thuật toán phân vùng đồ thị - Đã có rất nhiều nghiên cứu về các thuật toán heuristic để phát hiện ra sự phân chia nhỏ nhất của các đồ thị thưa thớt, đặc biệt là trong không gian của tính toán song song và thiết kế các mạch tích hợp. Việc chia nhỏ biểu đồ lân cận tạo ra nó có thể áp dụng để sử dụng các thuật toán phân vùng đồ thị cho giai đoạn phân nhóm như Opossum và Chameleon cần phân vùng đồ thị.
Việc chia nhỏ đồ thị tiệm cận phải được coi là một bước ban đầu trước khi cần đến các thuật toán phân cụm thực tế. Một sự thưa thớt tốt nhất có thể khiến ma trận gần nhau được chia thành các phần tử được kết nối tương quan với các cụm mong muốn, nhưng trên thực tế, điều này xuất hiện.
Nó chỉ đơn giản là cho một cạnh riêng lẻ để kết nối hai cụm hoặc một cụm riêng lẻ được chia thành nhiều cụm con không kết nối. Thật vậy, có thể thấy khi Jarvis-Patrick và SNN sử dụng phân nhóm dựa trên mật độ, biểu đồ tiệm cận thưa thớt được thay đổi để mang lại một biểu đồ tiệm cận mới. Biểu đồ tiệm cận mới này có thể được chia nhỏ. Các thuật toán phân cụm hoạt động với biểu đồ lân cận là kết quả của tất cả các quy trình tiền xử lý này.