Học Python qua các thuật toán Machine Learning cơ bản – Thuật toán k-Nearest Neighbors (kNN) (tt)

Trong bài trước, chúng ta đã tìm hiểu một vài khái niệm và thao tác toán học cơ bản trong thuật toán kNN đơn giản là tìm khoảng cách ngắn nhất từ k điểm đến một điểm bất kỳ. Toàn bộ nội dung của thuật toán này được tham khảo từ chương trình chương 2, mục 2.1, cuốn sách Machine Learning in Action như sau:


from numpy import *

import operator

import matplotlib.pyplot as plt

def createDataSet():

  group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])

  labels = ['A','B','C','D']

  return group, labels

def classify0(inX, dataSet, labels, k):

  dataSetSize = dataSet.shape[0]

  diffMat = tile(inX, (dataSetSize,1)) - dataSet

  sqDiffMat = diffMat**2

  sqDistances = sqDiffMat.sum(axis=1)

  distances = sqDistances**0.5

  sortedDistIndicies = distances.argsort()

  classCount={}

  for i in range(k):

    voteIlabel = labels[sortedDistIndicies[i]]

    classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1

    sortedClassCount = sorted(classCount.items(),

                key=operator.itemgetter(1), reverse=True)

  return sortedClassCount[0][0]

Nếu đọc kỹ bài trước (https://ngocminhtran.com/2020/02/16/hoc-python-qua-cac-thuat-toan-machine-learning-co-ban-thuat-toan-k-nearest-neighbors-knn/), chúng ta có thể hiểu được mục đích tính distances từ hàm classify0 (đây là phiên bản đơn giản và chúng ta sẽ tìm hiểu các phiên bản classify khác trong các bài sau). Bài viết này sẽ tiếp tục tìm hiểu Python thông qua phần còn lại của hàm classify0.

Khi kết thúc bài trước, chúng ta đã tính được vec tơ khoảng cách (Khoangcach):

Đây chính là distances trong hàm classify0. Kết quả cụ thể của distances là:

distances = Khoangcach = [ 1.48660687 1.41421356 0. 0.1 ]

Với vec tơ distances chúng ta đã xác định được các khoảng cách OM, ON, OP và OK và có thể biết được khoảng cách gần nhất là OP. Nhưng làm thế nào để chương trình biết điều đó đồng thời thuật toán kNN cũng phải chỉ ra lớp (hay label) của điểm (hay tập điểm) có khoảng cách gần điểm O nhất? Hiển nhiên là chúng ta có thể dự đoán là điểm P và lớp B.

Hàm argsort()

Mô đun NumPy của Python hỗ trợ hàm argsort() trả về vec tơ chỉ số được sắp xếp theo thứ tự tăng dần (theo giá trị tại chỉ số đó) từ một vec tơ cho trước với chú ý rằng các chỉ số bắt đầu từ 0. Xét đoạn mã sau từ hàm classify0:


sortedDistIndicies = distances.argsort()

sortedDistIndicies là vec tơ chỉ số được sắp tăng dần (theo gia trị) từ distances:

sortedDistIndicies = [2 3 1 0]

Ở đây 2 là chỉ số đầu tiên vì trong vec tơ distances giá trị tại chỉ số 2 là 0 là bé nhất, kế tiếp là 0.1 nên chỉ số là 3 và cứ thế.

Cấu trúc dictionary

Chúng ta để ý khai báo trong hàm classify0:


classCount={}

biến classCount có kiểu dữ liệu mà trong Python gọi là kiểu dictionary. Các phần tử trong một dictionary được có dạng cặp key:value hay rỗng (như khai báo biến classCount ở trên) như ví dụ sau:

dic = {“A”:3, “B”:2}

Ở đây, A và B là các key (hay khóa) và 3 và 2 là các value (hay giá trị tương ứng với key). Muốn biết giá trị của các key, chúng ta chỉ việc truy cập đến key đó như ví dụ:


print(dic['A']) # 3

print(dic['B']) # 2

Có hai chú ý:

Trong hai đoạn mã trên, tôi đã dùng ký hiệu # phía sau hai lệnh print. Trong Python, dấu # dùng để chú thích giống dấu // trong các ngôn ngữ họ C như C, C++, Java,…
Truy cập đến giá trị của một key nào đó dùng cặp ngoặc vuông kèm theo tên của key.

Tuy nhiên, nếu chúng ta truy cập đến giá trị của một key theo cách trên có thể dẫn tới lỗi nếu key không tồn tại trong dic. Ví dụ chúng ta gõ lệnh:


print(dic['C']) # phát sinh lỗi

Để giải quyết vấn đề này, Python cung cấp hàm get() như sau:


print(dic.get('C', 'Khoa khong ton tai!')) # Khoa khong ton tai

Tham số đầu tiên của get chính là key và tham số thứ hai là giá trị trả về nếu key đó không tồn tại trong dictionary (thay vì phát sinh lỗi).

Lúc này, chúng ta có thể hiểu được dòng lệnh:


classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1

hàm get bên phải sẽ trả về 0 nếu key voteIlabel không tồn tại trong classCount. Chúng ta phải cộng thêm 1 vì classCount ban đầu được khởi tạo là rỗng ({}).

Bên cạnh get(), Python còn hỗ trợ cho kiểu dictionary một hàm khác cũng phổ biến không kém là hàm items() dùng để trả về một danh sách (list) tất cả các cặp key/value của một dictionary. Ví dụ:


print(dic.items()) # dict_items([('A', 3), ('B', 2)])

Hàm sorted()

Việc sử dụng hàm items() trong dictionary sẽ hiệu quả hơn nếu được kết hợp với hàm sorted như đoạn lệnh kế tiếp trong classify0:


sortedClassCount = sorted(classCount.items(),

                    key=operator.itemgetter(1), reverse=True)

Một số chú ý:

Tham số đầu tiên của sorted chính là danh sách các cặp key/value từ dictionary (nhận được nhờ items()).
Tham số thứ hai là khóa mà chúng ta dựa vào đó để sắp xếp (lưu ý, key này không liên quan gì đến key/value trong dictionary) bằng cách dùng hàm opearator.itemgetter().Hàm operator.itemgetter() nhận một trong hai giá trị là 0 hay 1. Nếu giá trị nhận là 0 tức là chúng ta sẽ sắp xếp danh sách (tham số đầu tiên) dựa trên key từ các cặp key/value trong dictionary; ngược lại, nếu nhận là 1 thì dựa trên value.
Tham số cuối cùng quy định sắp xếp giảm dần nếu reverse = True, ngược lại sắp tăng dần. Mặc định reverse = False.

Xem xét kết quả từ đoạn mã sau:


dicSorted = sorted(dic.items(),key=operator.itemgetter(0), 
        
                     reverse=False)

print(dicSorted)

Kết quả là danh sách xếp tăng dần theo key:

[(‘A’, 3), (‘B’, 2)]

Thay đổi một ít để sắp tăng dần theo value:


dicSorted = sorted(dic.items(),key=operator.itemgetter(1), 
 
                 reverse=False)

print(dicSorted)

Kết quả:

[(‘B’, 2), (‘A’, 3)]

Các cặp trong danh sách trả về từ hàm sorted có thể được truy cập theo chỉ số, ví dụ truy cập đến cặp đầu tiên (sau khi được sắp) trong dicSorted:


dicSorted = sorted(dic.items(),key=operator.itemgetter(1), 

                   reverse=False)

print(dicSorted[0]) # ('B', 2)

Muốn hiển thị key của cặp thứ nhất:


print(dicSorted[0][0]) # B

Muốn hiển thị value của cặp thứ nhất:


print(dicSorted[0][1]) # 2

Cho đến lúc này chúng ta đã tìm hiểu chi tiết về cấu trúc dictionary và các hàm sắp xếp trong Python, trước khi xem lại toàn bộ hàm classify0 chúng ta sẽ xem xét cấu trúc lặp trong Python.

Cấu trúc lặp

Giống như hầu hết các ngôn ngữ lập trình, Python cung cấp hai lệnh lặp cơ bản là while và for. Nói về while và for trong Python có thể tìm thấy vô số tài liệu và ví dụ trên Internet và trong bài viết này sẽ không đề cập chi tiết vì mục đích của loạt bài này là chỉ bàn về các đặc trưng của Python trong khuôn khổ chương trình đang xét.

Trong hàm classify0 chúng ta bắt gặp lệnh for như sau:


for i in range(k):

Lệnh này thực thi các giá trị i =0, 1, 2,…,k-1 và kết thúc for (hay while) sẽ là dấu hai chấm. Ví dụ hiển thị các giá trị từ 0 đến 9, lệnh:


for i in range(10):

print(i)

Như vậy, chúng ta đã khám phá phần còn lại của thuật toán kNN tính khoảng cách ngắn nhất với các đặc trưng thú vị trong Python như dictionary, hàm get, hàm argsort, hàm sorted, for. Trong các bài viết kế tiếp chúng ta sẽ tìm hiểu các phiên bản phức tạp hơn của thuật toán kNN và qua đó cũng khám phá thêm nhiều đặc trưng thú vị khác trong Python.

Trần Ngọc Minh Notes

Stay hungry, stay foolish!