K-Nearest Neighbors và K-Means
K-Nearest Neighbors và K-Means: Hai Thuật Toán Dựa Trên Khoảng Cách Phổ Biến Trong Học Máy
Giới thiệu
Trong thế giới học máy, có nhiều thuật toán sử dụng khoảng cách làm nền tảng cho việc phân tích dữ liệu. Hai thuật toán nổi bật trong nhóm này là K-Nearest Neighbors (KNN) và K-Means Clustering. Mặc dù cả hai đều có chữ "K" trong tên và đều liên quan đến khoảng cách, chúng phục vụ cho những mục đích khác nhau và hoạt động theo những nguyên tắc khác nhau. Bài viết này sẽ giới thiệu chi tiết về cả hai thuật toán, giúp bạn hiểu rõ về cách thức hoạt động, ưu nhược điểm, và các ứng dụng thực tế của chúng.
K-Nearest Neighbors (KNN)
Thuật toán học có giám sát
K-Nearest Neighbors là một thuật toán học có giám sát (supervised learning), được sử dụng chủ yếu cho các bài toán phân loại (classification) và hồi quy (regression). KNN dựa trên một nguyên tắc đơn giản: một đối tượng được phân loại theo đa số trong K láng giềng gần nhất của nó.
Nguyên lý hoạt động
Thuật toán KNN hoạt động theo các bước sau:
Chọn số K: Xác định số lượng láng giềng gần nhất (K) mà bạn muốn xem xét.
Tính khoảng cách: Tính toán khoảng cách từ điểm dữ liệu mới đến tất cả các điểm trong tập huấn luyện. Các phép đo khoảng cách phổ biến bao gồm:
Khoảng cách Euclidean (phổ biến nhất): $\sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$
Khoảng cách Manhattan: $\sum_{i=1}^{n}|x_i - y_i|$
Khoảng cách Minkowski: $(\sum_{i=1}^{n}|x_i - y_i|^p)^{1/p}$
Xác định K láng giềng gần nhất: Sắp xếp các khoảng cách và xác định K điểm dữ liệu gần nhất.
Bầu chọn đa số hoặc tính trung bình:
Đối với bài toán phân loại: Lớp được gán cho điểm dữ liệu mới là lớp xuất hiện nhiều nhất trong K láng giềng.
Đối với bài toán hồi quy: Giá trị được dự đoán là giá trị trung bình của K láng giềng.
Trả về kết quả dự đoán.
Lựa chọn giá trị K
Việc lựa chọn giá trị K có ảnh hưởng lớn đến hiệu suất của thuật toán KNN:
K nhỏ: Làm cho mô hình nhạy cảm với nhiễu, có thể dẫn đến overfitting.
K lớn: Làm mô hình mượt hơn nhưng có thể bỏ qua các mẫu quan trọng, dẫn đến underfitting.
Một phương pháp phổ biến để chọn K là sử dụng K lẻ (tránh trường hợp hòa khi bầu chọn) và thực hiện cross-validation để tìm giá trị K tối ưu.
KNN có trọng số
Một biến thể của KNN là KNN có trọng số (Weighted KNN), trong đó các láng giềng gần hơn có ảnh hưởng lớn hơn đến kết quả dự đoán:
Trọng số thường được tính bằng nghịch đảo của khoảng cách: $w_i = \frac{1}{d(x, x_i)^2}$
Điều này giúp cải thiện độ chính xác trong nhiều trường hợp.
Ưu và nhược điểm của KNN
Ưu điểm:
Đơn giản, dễ hiểu và triển khai
Không cần huấn luyện, chỉ cần lưu trữ dữ liệu
Hiệu quả với tập dữ liệu nhỏ
Tự nhiên xử lý được các bài toán đa lớp
Dễ dàng cập nhật mô hình khi có dữ liệu mới
Nhược điểm:
Tốn kém về mặt tính toán và bộ nhớ khi tập dữ liệu lớn
Nhạy cảm với dữ liệu nhiễu
Hiệu suất giảm trong không gian có nhiều chiều (dimensional curse)
Cần chuẩn hóa dữ liệu trước khi sử dụng
Khó xử lý dữ liệu không cân bằng
Ví dụ Python với scikit-learn
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
# Tải dataset Iris
iris = load_iris()
X, y = iris.data, iris.target
# Chia dữ liệu thành tập huấn luyện và kiểm tra
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
# Khởi tạo mô hình KNN với K=5
knn = KNeighborsClassifier(n_neighbors=5)
# Huấn luyện mô hình
knn.fit(X_train, y_train)
# Dự đoán
y_pred = knn.predict(X_test)
# Đánh giá độ chính xác
accuracy = accuracy_score(y_test, y_pred)
print(f"Độ chính xác: {accuracy:.4f}")K-Means Clustering
Thuật toán học không giám sát
K-Means là một thuật toán học không giám sát (unsupervised learning), được sử dụng chủ yếu cho các bài toán phân cụm (clustering). Mục tiêu của K-Means là chia dữ liệu thành K cụm (clusters) dựa trên sự tương đồng giữa các điểm dữ liệu.
Nguyên lý hoạt động
Thuật toán K-Means hoạt động theo các bước sau:
Chọn số cụm K: Xác định số lượng cụm (K) mà bạn muốn chia dữ liệu.
Khởi tạo các tâm cụm: Chọn K điểm dữ liệu ngẫu nhiên làm tâm cụm ban đầu. Có nhiều phương pháp khởi tạo khác nhau, phổ biến nhất là phương pháp K-means++.
Gán điểm dữ liệu vào cụm gần nhất: Mỗi điểm dữ liệu được gán vào cụm có tâm gần nó nhất (dựa trên khoảng cách Euclidean).
Cập nhật tâm cụm: Tính toán lại tâm của mỗi cụm bằng cách lấy trung bình của tất cả các điểm dữ liệu trong cụm đó.
Lặp lại bước 3 và 4 cho đến khi các tâm cụm không thay đổi nhiều hoặc đạt đến số lần lặp tối đa.
Lựa chọn số cụm K
Việc lựa chọn số cụm K là một thách thức trong K-Means. Có một số phương pháp phổ biến để xác định K:
Phương pháp Elbow: Vẽ đồ thị tổng bình phương khoảng cách (WCSS) theo K và tìm "khuỷu tay" - điểm mà tốc độ giảm của WCSS chậm lại đáng kể.
Silhouette Score: Đo lường mức độ phù hợp của một điểm dữ liệu trong cụm của nó so với các cụm khác. Giá trị cao hơn chỉ ra rằng các cụm được tách biệt tốt.
Gap Statistic: So sánh tổng biến thiên trong cụm với giá trị kỳ vọng theo phân phối tham chiếu.
K-Means++
K-Means++ là một cải tiến của K-Means, tập trung vào việc cải thiện phương pháp khởi tạo tâm cụm:
Chọn một điểm dữ liệu ngẫu nhiên làm tâm cụm đầu tiên.
Đối với mỗi điểm dữ liệu, tính khoảng cách đến tâm cụm gần nhất đã biết.
Chọn điểm dữ liệu tiếp theo làm tâm cụm với xác suất tỷ lệ thuận với bình phương khoảng cách.
Lặp lại bước 2 và 3 cho đến khi chọn đủ K tâm cụm.
K-Means++ giúp giảm khả năng hội tụ đến cực tiểu cục bộ.
Ưu và nhược điểm của K-Means
Ưu điểm:
Đơn giản, dễ hiểu và triển khai
Hiệu quả tính toán (O(n×K×I×d), với n là số điểm dữ liệu, K là số cụm, I là số lần lặp, và d là số chiều)
Hoạt động tốt với dữ liệu có dạng cụm tròn
Dễ dàng diễn giải kết quả
Có thể mở rộng cho dữ liệu lớn
Nhược điểm:
Cần xác định trước số cụm K
Nhạy cảm với việc khởi tạo tâm cụm ban đầu
Không hiệu quả với dữ liệu có dạng cụm phức tạp (không tròn)
Nhạy cảm với dữ liệu ngoại lai
Kết quả có thể khác nhau giữa các lần chạy do yếu tố ngẫu nhiên
Ví dụ Python với scikit-learn
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import numpy as np
# Tạo dữ liệu mẫu
X, y = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)
# Khởi tạo mô hình K-Means với K=4
kmeans = KMeans(n_clusters=4, init='k-means++', random_state=0)
# Huấn luyện mô hình
kmeans.fit(X)
# Lấy nhãn cụm và tâm cụm
labels = kmeans.labels_
centers = kmeans.cluster_centers_
# Vẽ kết quả
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', alpha=0.7)
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=200, alpha=0.8, marker='X')
plt.title('K-Means Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()
# Tính WCSS cho phương pháp Elbow
wcss = []
for i in range(1, 11):
kmeans = KMeans(n_clusters=i, init='k-means++', random_state=0)
kmeans.fit(X)
wcss.append(kmeans.inertia_)
# Vẽ đồ thị Elbow
plt.figure(figsize=(10, 6))
plt.plot(range(1, 11), wcss, marker='o', linestyle='-')
plt.title('Phương pháp Elbow')
plt.xlabel('Số cụm (K)')
plt.ylabel('WCSS')
plt.show()So sánh KNN và K-Means
Mặc dù cả KNN và K-Means đều liên quan đến khoảng cách và tham số K, chúng có những điểm khác biệt cơ bản:
Loại học máy
Học có giám sát
Học không giám sát
Mục đích
Phân loại hoặc hồi quy
Phân cụm
Ý nghĩa của K
Số láng giềng gần nhất
Số cụm
Thời điểm tính toán
Thời điểm dự đoán (lazy learning)
Thời điểm huấn luyện (eager learning)
Dữ liệu đầu vào
Dữ liệu có nhãn
Dữ liệu không có nhãn
Đầu ra
Nhãn dự đoán (phân loại) hoặc giá trị (hồi quy)
Phân cụm của dữ liệu và tâm cụm
Độ phức tạp thời gian
O(n×d) cho mỗi lần dự đoán
O(n×K×I×d) cho huấn luyện
Ứng dụng thực tế
Ứng dụng của KNN
Hệ thống gợi ý: Gợi ý sản phẩm, phim, bài hát dựa trên sở thích của người dùng tương tự.
Nhận dạng chữ viết tay: Phân loại các ký tự viết tay dựa trên sự tương đồng với các mẫu đã biết.
Phân tích tín dụng: Xác định rủi ro cho vay dựa trên hồ sơ của các khách hàng tương tự.
Nhận dạng khuôn mặt: So sánh khuôn mặt với cơ sở dữ liệu các khuôn mặt đã biết.
Dự đoán giá cả: Dự đoán giá nhà, xe dựa trên các tài sản tương tự.
Ứng dụng của K-Means
Phân khúc khách hàng: Nhóm khách hàng dựa trên hành vi mua hàng và đặc điểm nhân khẩu học.
Nén hình ảnh: Giảm số lượng màu sắc trong hình ảnh bằng cách nhóm các màu tương tự.
Phân tích văn bản: Nhóm các tài liệu tương tự hoặc phát hiện chủ đề.
Giám sát bất thường: Phát hiện các mẫu bất thường trong dữ liệu.
Phân tích thị trường chứng khoán: Nhóm các cổ phiếu có xu hướng biến động tương tự.
Cải tiến và biến thể
Cải tiến cho KNN
Ball Tree và KD Tree: Cấu trúc dữ liệu để tăng tốc tìm kiếm láng giềng gần nhất.
Approximate Nearest Neighbors: Phương pháp tìm kiếm xấp xỉ để tăng hiệu suất với dữ liệu lớn.
Local Sensitive Hashing (LSH): Kỹ thuật băm để giảm số lượng so sánh cần thiết.
KNN với thuật toán Condensed Nearest Neighbor: Giảm kích thước tập dữ liệu huấn luyện.
Cải tiến cho K-Means
Mini-Batch K-Means: Sử dụng các mini-batch ngẫu nhiên để tăng tốc độ hội tụ.
K-Medoids (PAM): Sử dụng các điểm dữ liệu thực làm tâm cụm thay vì điểm trung bình.
Bisecting K-Means: Phương pháp phân cụm phân cấp từ trên xuống.
Spherical K-Means: Phiên bản K-Means hoạt động trên dữ liệu chuẩn hóa đơn vị.
Gaussian Mixture Models (GMM): Mở rộng của K-Means cho phép các cụm có hình dạng elip và các điểm có xác suất thuộc về nhiều cụm.
Khi nào sử dụng KNN và khi nào sử dụng K-Means?
Khi nào sử dụng KNN?
Khi bạn có dữ liệu đã được gán nhãn
Khi bạn muốn thực hiện phân loại hoặc hồi quy
Khi tập dữ liệu không quá lớn
Khi bạn cần một mô hình dễ hiểu và diễn giải
Khi bạn không cần một mô hình tổng quát (chỉ cần dự đoán từng trường hợp)
Khi nào sử dụng K-Means?
Khi bạn không có dữ liệu được gán nhãn trước
Khi bạn muốn khám phá cấu trúc hoặc mẫu tiềm ẩn trong dữ liệu
Khi bạn cần phân nhóm dữ liệu thành các cụm riêng biệt
Khi bạn biết hoặc có thể ước tính số lượng cụm cần tạo
Khi dữ liệu của bạn có xu hướng hình thành các cụm hình tròn
Kết luận
K-Nearest Neighbors và K-Means là hai thuật toán cơ bản nhưng mạnh mẽ trong học máy, với những ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau. Mặc dù cả hai đều sử dụng khoảng cách và tham số K, chúng phục vụ cho những mục đích khác nhau: KNN là một thuật toán học có giám sát dùng cho phân loại và hồi quy, trong khi K-Means là một thuật toán học không giám sát dùng cho phân cụm.
Việc hiểu rõ về cách thức hoạt động, ưu nhược điểm, và các tình huống phù hợp để áp dụng từng thuật toán sẽ giúp bạn lựa chọn công cụ phù hợp cho bài toán cụ thể. Cả hai thuật toán đều có những cải tiến và biến thể để khắc phục các hạn chế của phiên bản cơ bản, giúp chúng vẫn còn hữu ích và phổ biến trong thời đại học sâu (deep learning) hiện nay.
Tài liệu tham khảo
Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 21-27.
MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1, 281-297.
Arthur, D., & Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1027-1035.
Scikit-learn: Machine Learning in Python, Pedregosa et al., JMLR 12, pp. 2825-2830, 2011.
Müller, A. C., & Guido, S. (2016). Introduction to Machine Learning with Python: A Guide for Data Scientists. O'Reilly Media.
Last updated