Quá trình kết hợp một tập hợp các đối tượng vật lý hoặc trừu tượng thành các lớp của các đối tượng giống nhau được gọi là phân cụm. Cụm là một tập hợp các đối tượng dữ liệu giống nhau trong cùng một cụm và khác biệt với các đối tượng trong các cụm khác. Một nhóm các đối tượng dữ liệu có thể được coi là một nhóm trong một số ứng dụng. Phân tích cụm là một hoạt động thiết yếu của con người.
Phân cụm hỗ trợ trong việc xác định các ngoại lệ. Các giá trị giống nhau được tổ chức thành các cụm và những giá trị nằm ngoài cụm được gọi là giá trị ngoại lai. Kỹ thuật phân cụm coi các bộ dữ liệu là các đối tượng. Chúng phân vùng các đối tượng thành các nhóm hoặc cụm để các đối tượng trong một cụm là “tương tự” với nhau và “không giống” với các đối tượng trong các cụm khác. Nó thường được định nghĩa về mức độ "gần" của các đối tượng trong không gian, dựa trên hàm khoảng cách.
Có nhiều cách tiếp cận khác nhau về phân nhóm dựa trên đồ thị như sau -
Chia nhỏ biểu đồ lân cận để chỉ duy trì liên kết của một đối tượng với các đối tượng lân cận gần nhất của nó. Sự thưa thớt này có lợi cho việc quản lý tiếng ồn và các yếu tố ngoại lai. Nó cũng cho phép sử dụng các thuật toán phân vùng đồ thị cực kỳ hiệu quả đã được tạo ra cho các đồ thị thưa thớt.
Nó có thể đại diện cho một thước đo độ giống nhau giữa hai đối tượng dựa trên một số hàng xóm gần nhất mà chúng gửi đến. Phương pháp này phụ thuộc vào quan sát rằng một đối tượng và các đối tượng lân cận nói chung thuộc cùng một lớp, có lợi cho việc khắc phục các vấn đề có kích thước cao và các cụm có mật độ thay đổi.
Nó có thể đại diện cho các đối tượng cốt lõi và phát triển các cụm xung quanh chúng. Trong phân cụm dựa trên đồ thị, điều cần thiết là phải đưa ra khái niệm dựa trên mật độ dựa trên một đồ thị tiệm cận hoặc một biểu đồ tiệm cận thưa thớt. Cũng như với DBSCAN, việc phát triển các cụm xung quanh các đối tượng cốt lõi dẫn đến cách tiếp cận phân nhóm có thể khám phá các cụm có hình dạng và kích thước khác nhau.
Nó có thể sử dụng dữ liệu trong biểu đồ lân cận để hỗ trợ tính toán phức tạp hơn về việc liệu hai cụm có nên được kết hợp hay không. Riêng hai cụm chỉ được kết hợp nếu cụm kết quả sẽ có các đặc điểm giống với hai cụm ban đầu.
Nó có thể bắt đầu bằng cách thảo luận về sự thưa thớt của đồ thị lân cận, hỗ trợ hai trường hợp kỹ thuật có phương pháp phân cụm dựa trên cách tiếp cận này, chẳng hạn như MST giống với thuật toán phân cụm kết nối đơn và Opossum.
Một thuật toán phân cụm phân cấp cần một khái niệm tự tương tự để xác định xem có nên kết hợp các cụm hay không. Nó có thể xác định độ tương tự của Shared Nearest Neighbor (SNN), một phép đo độ tương tự mới) và học thuật toán phân nhóm Jarvis-Patrick, thuật toán cần sự tương tự này.