Xu hướng phát triển công nghệ thông tin ngày càng tăng, song song với nó lượng dữ liệu được sinh ra cũng ngày một lớn. Vì vậy nhu cầu để xử lý dữ liệu cũng lớn hơn, Machine Learning đang góp phần giải quyết vấn đề này. Trong bài này tôi trình bày một trong những thuật toán thường dùng trong machine learning đó là "Thuật toán k láng giềng gần" K-Nearest Neighbour
I. Đặt vấn đề
Giả sử một nhóm triển khai dịch vụ Quản Lý Ca ở thị trường Việt Nam hiện tại có hai vị trí là Sale và Tech. Hai vị trí này được đánh số điểm "Kỹ thuật" và "Kỹ năng mềm" khác nhau, từ những số điểm tôi sẽ gắn nhãn cho từng thành viên
h1
h2
Trong số những thành viên kể trên có duy nhất một người chưa được gắn nhãn là "Hoàng Anh", bài toán đặt ra là dựa theo dữ liệu có sẵn hãy phán đoán xem Hoàng Anh thuộc nhãn gì hay Hoàng Anh là Tech hay Sale.
Chúng ta xử lý bài toán này bằng cách đo khoảng cách hình học điểm "Kỹ thuật" và điểm "Kỹ năng mềm" của Hoàng Anh tới các thành viên khác, ta chọn ra ba thành viên gần nhất và hai trong số ba thành viên gần nhất có nhãn giống nhau và nhãn Hoàng Anh sẽ thuộc về đa số. Cụ thể hình h1, ta có thể kết luận Hoàng Anh được sẽ gắn nhãn là Tech. Vì khoảng cách của điểm kỹ năng của Hoàng Anh gần với hai thành viên mang nhãn Tech là Thành và Đạt và một thành viên mang nhãn Sale là An.
Chi tiết hơn, ta coi điểm "Tech" là trục y và điểm "Kỹ năng mềm" là trục x, dựa vào công thức ở hình h2 ta có kết quả ở cột khoảng cách như sau.
Ví dụ ta tính khoảng cách giữa Tuyết và Hoàng Anh thì công thức sẽ là
SQRTPI(POWER(4.5-7,2) + POWER(8.7 - 3,2)) = 11.03201248※Công thức trên được tính bằng Excel
II. Thực thi bài toán cụ thể bằng python
Trong ví dụ tiếp theo sử dụng ba thư viện của python đó là cv2(OpenCV), numpy, matplotlib
Tạo ra một loạt đối tượng hình vuông, hình tam giác. Sau đó tạo ngẫu nhiên một hình tròn và phán đoán xem hình tròn đó là hình thuộc loại hình vuông hay hình tam giác.
Đầu tiên lấy ngẫu nhiên 25 phần từ từ 0 tới 100 và lấy ngẫu nhiên 25 phần từ 0 và 1 như sau:
import cv2
import numpy as np
import matplotlib.pyplot as plt
# Lấy ngẫu nhiên 25 phần tử từ 0 tới 100 và gán nó kiểu số thực mảng hai chiều
trainData = np.random.randint(0, 100, (25, 2)).astype(np.float32)
# Lấy ngẫu nhiên 25 phần từ 0 và 1
ketqua = np.random.randint(0, 2, (25, 1)).astype(np.float32)
print trainData
print ketquaOutput:
$ python knearestbeighbour.py
[[ 7. 53.]
[54. 69.]
[45. 20.]
[16. 43.]
[97. 37.]
[ 7. 28.]
[46. 85.]
[69. 10.]
[64. 73.]
[59. 90.]
[37. 43.]
[19. 32.]
[25. 7.]
[15. 85.]
[49. 83.]
[17. 69.]
[87. 29.]
[95. 11.]
[79. 35.]
[ 9. 66.]
[45. 29.]
[47. 32.]
[87. 84.]
[83. 47.]
[39. 40.]]
[[0.]
[1.]
[1.]
[1.]
[0.]
[0.]
[1.]
[1.]
[0.]
[0.]
[1.]
[1.]
[1.]
[0.]
[1.]
[0.]
[1.]
[1.]
[0.]
[0.]
[0.]
[0.]
[1.]
[1.]
[0.]]Tiếp theo, ở mảng ketqua ta quy định "Hình vuông" là 1 và "Hình tam giác" là 0, đồng thời tạo ra một phần tử random như sau:
....
# Lấy những phần tử có ketqua = 1 từ traindata
red = trainData[ketqua.ravel() == 1]
# Lấy những phần tử cso ketqua = 0 từ traindata
blue = trainData[ketqua.ravel() == 0]
#Lấy ngẫu nhiên một một phần tử trong khoảng từ 0 và 100
newMember = np.random.randint(0, 100, (1, 2)).astype(np.float32)
# Ta In kết quả ra như sau
print '======Red ============'
print red
print '======blue ============'
print blue
print '======New member ============'
print newMember
Output:
$ python knearestbeighbour.py
======Red ============
[[39. 89.]
[78. 12.]
[21. 84.]
[79. 40.]
[ 1. 38.]
[82. 51.]
[18. 31.]
[62. 11.]
[ 0. 2.]
[67. 7.]
[ 6. 82.]
[18. 71.]
[18. 71.]]
======blue ============
[[12. 90.]
[94. 62.]
[80. 41.]
[ 7. 38.]
[ 1. 64.]
[67. 68.]
[74. 6.]
[40. 37.]
[ 8. 14.]
[12. 5.]
[71. 6.]
[11. 79.]]
======New member ============
[[19. 82.]]Tiếp theo, ta dùng thư viện matplotlib để hiển thị các hình vuông, hình tam giác, hình tròn.
......
plt.scatter(red[:, 0], red[:, 1], 100, 'r', 's')
plt.scatter(blue[:, 0], blue[:, 1], 100, 'b', '^')
plt.scatter(newMember[:, 0], newMember[:, 1], 100, 'g', 'o')
plt.show()Output:
Hình tròn xanh chính là phần tử ngẫu nhiên mà chưa biết thuộc nhóm vuông hay tam giác
Bây giờ, sẽ dùng thuật toán K-Nearest Neighbour để tìm xem hình tròn nó gần nhất với nhiều hình vuông hơn hay tam giác hơn. ta tìm ba phần gần nhất nếu phần tử nào chiếm đa số thì kết luận hình tròn sẽ thuộc lớp đó. Có nghĩa là gần nhất những thằng nào thì cùng loại với nó.
....
# Khởi tạo thuạt toán KNearest
knn = cv2.ml.KNearest_create()
# Training data
knn.train(trainData, 0, ketqua)
# In kêt quả resut = 1 => vuông, 0 -> tam giác
temp, result, nearest, distance = knn.findNearest(newMember, 3)
print("Result: {}\n".format(result))
print("Nearest: {}\n".format(nearest))
print("Distance: {}\n".format(distance))
plt.show()Output:
Result: [[0.]]
Nearest: [[0. 0. 0.]]
Distance: [[400. 442. 521.]]Quan sát hình trên sẽ thấy, hình tròn thuộc lớp tam giác do nó gần những thằng tam giác nhất.
Code đầy đủ:
import cv2
import numpy as np
import matplotlib.pyplot as plt
trainData = np.random.randint(0, 100, (25, 2)).astype(np.float32)
ketqua = np.random.randint(0, 2, (25, 1)).astype(np.float32)
red = trainData[ketqua.ravel() == 1]
blue = trainData[ketqua.ravel() == 0]
newMember = np.random.randint(0, 100, (1, 2)).astype(np.float32)
plt.scatter(red[:, 0], red[:, 1], 100, 'r', 's')
plt.scatter(blue[:, 0], blue[:, 1], 100, 'b', '^')
plt.scatter(newMember[:, 0], newMember[:, 1], 100, 'g', 'o')
knn = cv2.ml.KNearest_create()
knn.train(trainData, 0, ketqua)
temp, result, nearest, distance = knn.findNearest(newMember, 3)
print("Result: {}\n".format(result))
print("Nearest: {}\n".format(nearest))
print("Distance: {}\n".format(distance))
plt.show()III. Kết luận
Trên đây tôi trình bày cách thực thi thuật toán k láng giềng gần nhất(K-Nearest Neighbour) bằng một ví dụ đơn giản nhất. Bài viết này tôi muốn trình bày những vấn đề phức tạp một cách đơn giản và dễ hiểu nhất, bằng những ví dụ đơn giản nhất. Hy vọng giúp ích được phần nào đó cho độc giả.
