Bài viết sưu tầm

Đầu vào: Ma trận dữ liệu X ∈ R ^d×N và số lượng cluster cần tìm K < N.

Đầu ra: Ma trận các centroid M ∈ R ^d×K và ma trận label Y ∈ R ^N×K.

Bước 1. Chọn K điểm bất kỳ trong training set làm các centroid ban đầu.

Bước 2. Phân mỗi điểm dữ liệu vào cluster có centroid gần nó nhất.

Bước 3. Nếu việc phân nhóm dữ liệu vào từng cluster ở bước 2 không thay đổi so với vòng lặp trước nó thì ta dừng thuật toán.

Bước 4. Cập nhật centroid cho từng cluster bằng cách lấy trung bình cộng của tất các các điểm dữ liệu đã được gán vào cluster đó sau bước 2.

Bước 5. Quay lại bước 2.

Thuật toán này được đảm bảo sẽ hội tụ sau một số hữu hạn vòng lặp. Thật vậy, vì hàm mất mát là một số dương và sau mỗi bước 2 hoặc 3, giá trị của hàm mất mát bị giảm đi. Vậy, dãy số biểu diễn giá trị của hàm mất mát sau mỗi bước là một đại lượng không tăng và bị chặn dưới, điều này chỉ ra rằng dãy số này phải hội tụ. Để ý thêm nữa, số lượng cách phân nhóm cho toàn bộ dữ liệu là hữu hạn (khi số cluster K là cố định) nên đến một lúc nào đó, hàm mất mát sẽ không thể thay đổi, và chúng ta có thể dừng thuật toán tại đây. Nếu tồn tại một cluster không chứa điểm nào, mẫu số sẽ bằng không, và phép chia sẽ không thực hiện được. Vì vậy, K điểm bất kỳ trong training set được chọn làm các centroid ban đầu ở Bước 1. để đảm bảo rằng mỗi cluster có ít nhất một điểm. Trong quá trình huấn luyện, nếu tồn tại một cluster không chứa điểm nào, có hai cách giải quyết. Cách thứ nhất là bỏ đi cluster đó và giảm K đi một. Cách thứ hai là thay centroid của cluster đó bằng một điểm bất kỳ trong training set, chẳng hạn, điểm xa centroid hiện tại của nó nhất.

Machine Learning cơ bản ( Vũ Hữu Tiệp)