Thuật toán Bisecting K-means là một mở rộng đơn giản của thuật toán K-means cơ bản dựa trên một khái niệm đơn giản: để có K cụm, chia tập hợp các điểm thành hai cụm, chọn một trong các cụm này để chia, v.v., cho đến khi đã tạo ra K cụm.
Thuật toán K-means nhận tham số đầu vào k, và chia một tập n đối tượng thành k cụm sao cho độ tương đồng nội cụm kết quả cao nhưng độ tương đồng giữa các cụm thấp. Độ tương đồng cụm được đánh giá liên quan đến giá trị trung bình của các đối tượng trong một cụm, có thể được xem là tâm cụm hoặc trọng tâm.
Các giá trị ban đầu cho các trung bình được gán tùy ý. Chúng có thể được gán ngẫu nhiên hoặc có thể dùng các giá trị từ k mục nhập đầu tiên. Điều kiện hội tụ có thể dựa trên sai số bình phương, nhưng không bắt buộc. Ví dụ, thuật toán được gán cho nhiều cụm. Các phương pháp dừng khác đơn giản khóa tại một số lần lặp cố định. Số lần lặp tối đa có thể được bao gồm để đảm bảo dừng ngay cả khi không hội tụ.
Thuật toán Bisecting K-Means như sau:
Khởi tạo danh sách cụm chứa cụm bao gồm tất cả các điểm.
lặp lại
Loại bỏ một cụm khỏi danh sách cụm.
{Thực hiện nhiều lần "thử" chia đôi cụm đã chọn.}
với i: 1 đến số lần thử
Chia đôi cụm đã chọn sử dụng K-means cơ bản.
kết thúc cho
Chọn hai cụm từ lần chia đôi có tổng SSE nhỏ nhất.
Chèn hai cụm này vào danh sách cụm.
cho đến khi danh sách cụm chứa K cụm.
Có một số cách để chọn cụm nào để chia. Có thể chọn cụm lớn nhất ở mỗi bước, chọn cái có SSE lớn nhất, hoặc dùng tiêu chí dựa trên cả kích thước và SSE. Các lựa chọn khác nhau dẫn đến các cụm khác nhau.
Có thể tinh chỉnh các cụm kết quả bằng cách sử dụng các tâm của chúng làm tâm ban đầu cho thuật toán K-means cơ bản. Điều này cần thiết vì mặc dù thuật toán K-means được bảo đảm tìm thấy một phân cụm định nghĩa cực tiểu cục bộ về SSE, trong Bisecting K-means nó dùng thuật toán K-means "cục bộ", tức là để chia các cụm đơn lẻ. Do đó, tập hợp cụm cuối cùng không định nghĩa một phân cụm là cực tiểu cục bộ về tổng SSE.
Cuối cùng, bằng cách ghi lại chuỗi các phân cụm được tạo ra khi K-means chia các cụm, cũng có thể dùng Bisecting K-means để tạo một phân cụm phân cấp.