Scikit-learn: K-nearest neighbors

knn concept

knn concept

Trong bài viết này, ta sẽ tìm hiểu thuật toán K-láng giềng gần (K-nearest neighbors (KNN)). KNN thuộc nhóm phương pháp phân lớp dựa trên thể hiện (instance-based classification). Tôi sẽ trình bày ý tưởng đơn giản về thuật toán này. Sau đó, ta sẽ sử dụng thư viện scikit-learn phục vụ cho việc cài đặt mô hình dự đoán KNN.

Ý tưởng

Hãy cho tôi biết bạn của bạn là ai, tôi sẽ cho bạn biết bạn là người như thế nào.

Đó là một câu danh ngôn mà có lẽ ai cũng biết. Và có lẽ, phần lớn đều đồng ý. Đây là ý tưởng đằng sau thuật toán KNN. Để dự đoán mẫu dữ liệu mới x_new thuộc về lớp nào, ta dựa vào số k dữ liệu gần nó nhất. Ví dụ k = 3, nghĩa là gần x_new có 3 điểm dữ liệu. Giả sử trong đó có 2 điểm dữ liệu thuộc về lớp B và 1 điểm dữ liệu thuộc về lớp A. Như vậy, ta sẽ gán x_new thuộc về lớp B do x_new có 2 điểm dữ liệu thuộc lớp B gần nó nhất.

Thuật toán

kNN Algorithm

kNN Algorithm

Thuật toán xác định lớp cho mẫu mới x_new

  • Tính khoảng cách giữa x_new và tất cả các mẫu trong tập huấn luyện
  • Chọn k mẫu gần nhất với x_new trong tập huấn luyện
  • Gán x_new vào lớp có nhiều mẫu nhất trong số k mẫu láng giềng đó (hoặc x_new nhận giá trị trung bình của k mẫu)

Đánh giá

Ưu điểm

  • Dễ sử dụng và cài đặt
  • Xử lý tốt với dữ liệu nhiễu (do dựa trên khoảng cách để quyết định phân lớp)

Khuyết điểm

  • Cần lưu tất cả các mẫu để dự đoán
  • Cần nhiều thời gian để xác định lớp cho một mẫu mới (cần tính và so sánh khoảng cách đến tất cả các mẫu huấn luyện)
  • Phụ thuộc vào giá trị k do người dùng lựa chọn. Nếu k quá nhỏ, nhạy cảm với nhiễu. Nếu k quá lớn, vùng lân cận có thể chứa các điểm của lớp khác.
  • Cần chuyển đổi kiểu dữ liệu với thuộc tính phi số (categorial)

Ví dụ minh hoạ

Ta sẽ sử dụng thuật toán KNN của scikit-learn để phân lớp dữ liệu với tập huấn luyện là Iris. Tập dữ liệu hoa Iris được Ronald Fisher giới thiệu vào năm 1936. Tập dữ liệu này được dùng cho các bài toán phân lớp. Dữ liệu gồm 50 mẫu thu thập từ ba loại hoa Iris (Iris setosa, Iris virginica và Iris versicolor). Bốn thuộc tính cho mỗi mẫu gồm chiều dài và chiều rộng của đài hoa và cánh hoa được tính theo đơn vị centimet.

# 6 dòng dữ liệu đầu tiên của tập dữ liệu Iris
5.3,3.7,1.5,0.2,Iris-setosa
5.0,3.3,1.4,0.2,Iris-setosa
7.0,3.2,4.7,1.4,Iris-versicolor
6.4,3.2,4.5,1.5,Iris-versicolor
6.3,3.3,6.0,2.5,Iris-virginica
5.8,2.7,5.1,1.9,Iris-virginica

Tiếp theo, ta sẽ cài đặt chương trình minh hoạ cho thuật toán KNN.

# k-Nearest Neighbor
from sklearn import datasets
from sklearn import metrics
from sklearn.neighbors import KNeighborsClassifier

# load iris the datasets
dataset = datasets.load_iris()

# fit a k-nearest neighbor model to the data
model = KNeighborsClassifier()
model.fit(dataset.data, dataset.target)
print(model)
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
           metric_params=None, n_neighbors=5, p=2, weights='uniform')

# make predictions
expected = dataset.target
predicted = model.predict(dataset.data)

# summarize the fit of the model
print(metrics.classification_report(expected, predicted))
             precision    recall  f1-score   support

          0       1.00      1.00      1.00        50
          1       0.96      0.94      0.95        50
          2       0.94      0.96      0.95        50

avg / total       0.97      0.97      0.97       150

print(metrics.confusion_matrix(expected, predicted))
[[50  0  0]
 [ 0 47  3]
 [ 0  2 48]]
iris knn

iris knn

Qua ví dụ trên, ta thấy thuật toán KNN ứng dụng khá tốt trên tập dữ liệu Iris. KNN cho độ chính xác (precision) trung bình là 97%, (recall) trung bình là 97%, và (f1-score) là 97%. Để cài đặt thuật toán, ta chỉ cần khai báo lớp KNeighborsClassifier và gọi hàm fit() ứng với mô hình phân lớp này.

Advertisements

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s