Lập trình

K-NN là một thuật toán có thể được sử dụng khi bạn có một loạt các đối tượng đã được xếp hạng hoặc được dán nhãn một cách nào đó, và các đối tượng tương tự khác đã không được phân loại, dán nhãn nào, và bạn muốn có một cách để tự động ghi nhãn.

Các đối tượng có thể là các nhà khoa học dữ liệu đã được phân lớp là "sexy" hay "không sexy"; hoặc những người đã được dán nhãn là "tín nhiệm cao" hoặc "tín dụng thấp"; hoặc các nhà hàng đã được gắn nhãn "năm sao", "bốn sao", "ba sao", "hai ngôi sao", "một ngôi sao", hoặc nếu họ thực sự hút, "không sao." Nghiêm trọng hơn, nó có thể là bệnh nhân đã được phân loại là "nguy cơ ung thư cao" hay "nguy cơ ung thư thấp."

Bạn phải mất một giây và suy nghĩ hay không hồi quy tuyến tính sẽ thực hiện để giải quyết các vấn đề thuộc loại này.

Tốt, vậy câu trả lời là: nó phụ thuộc. Khi bạn sử dụng hồi quy tuyến tính, đầu ra là một biến liên tục. Ở đây, đầu ra của thuật toán của bạn sẽ là một nhãn phân loại, vì vậy hồi quy tuyến tính sẽ không giải quyết được các vấn đề như nó được mô tả.

Tuy nhiên, nó không phải không thể giải quyết nó với hồi quy tuyến tính cộng với các khái niệm về một "ngưỡng". Ví dụ, nếu bạn đang cố gắng để dự đoán điểm số tín dụng của người dân từ các lứa tuổi và thu nhập của họ, và sau đó chọn một ngưỡng như 700 như vậy là nếu dự đoán của bạn cho một người nào đó có số tuổi và thu nhập của bạn quan sát được trên 700, bạn muốn dán nhãn tín dụng dự đoán của họ là "cao", hoặc quăng chúng vào một thùng được dán nhãn "cao". Nếu không, bạn muốn ném chúng vào thùng dán nhãn "thấp". Với ngưỡng hơn, bạn cũng có thể có loại có hạt nhỏ hơn như "rất thấp", "thấp", "trung bình", "cao" và "rất cao".

Để làm điều đó theo cách này, với hồi quy tuyến tính bạn phải thiết lập các thùng như phạm vi của một đầu ra liên tục. Nhưng không phải tất cả mọi thứ trên thang điểm liên tục như một số điểm tín dụng. Ví dụ, nếu các nhãn của bạn là "có khả năng đảng Dân chủ", "có khả năng đảng Cộng hòa", và "có khả năng độc lập"? Bạn sẽ làm gì bây giờ?

Các trực giác đằng sau k-NN là xem xét các mục khác tương tự nhất về định nghĩa các thuộc tính của chúng, nhìn vào nhãn của họ, và cung cấp cho các mục không được gán các đa số phiếu. Nếu có một cà vạt, bạn lựa chọn ngẫu nhiên trong số các nhãn đã gắn đầu tiên.

Vì vậy, với ví dụ, nếu bạn đã có một loạt các phim được dán nhãn " thumbs up " hoặc " thumbs down  ”, và bạn đã có một bộ phim được gọi là " Data Gone Wild " đã không được đánh giá bạn có thể xem các thuộc tính của nó: chiều dài của bộ phim, thể loại, số lượng những cảnh quan hệ tình dục, số thắng diễn viên thắng Oscar trong nó, và ngân sách của bộ phim. Sau đó bạn có thể tìm thấy bộ phim khác với các thuộc tính tương tự, nhìn vào xếp hạng của chúng, và sau đó cung cấp cho "Data Gone Wild" một đánh giá mà không bao giờ phải xem nó.

Để tự động hoá nó, có 2 quyết định phải được thực hiện: đầu tiên, làm thế nào để bạn xác định tương tự (similarity) hoặc gần gũi? Một khi bạn xác định nó, cho một mục chưa được xếp hạng nhất định, bạn có thể nói như thế nào tương tự như tất cả các mặt hàng được dán nhãn là nó, và bạn có thể lấy các items tương tự nhất (most similar) và gọi họ là láng ghiềng (neighbors), mỗi người có một "cuộc bỏ phiếu".

Điều này mang đến cho bạn để quyết định thứ hai: làm thế nào nhiều láng giềng, bạn nên xem xét hoặc "chúng ta hãy bỏ phiếu"? Giá trị này là k, mà cuối cùng bạn sẽ lựa chọn như các nhà khoa học dữ liệu, và chúng tôi sẽ cho bạn biết làm thế nào.

Có lý? Hãy thử với một ví dụ thực tế hơn.

Ví dụ với điểm số tín dụng

Giả sử bạn có tuổi, thu nhập, và một loại tín dụng cao hay thấp, và thuộc một nhóm của mọi người và bạn muốn sử dụng các độ tuổi và thu nhập để dự đoán các nhãn tín dụng "cao" hay "thấp" cho một người mới.

Với ví dụ, ở đây ta có vài hàng đầu tiên của một tập dữ liệu, với thu nhập hiện trong hàng ngàn người:

age income credit

69	3	low
66	57	low
49	79	low
49	17	low
58	26	high
44	71	High

Bạn có thể vẽ mọi người như các điểm trên mặt phẳng và nhãn của mọi người với một vòng tròn trống nếu họ có xếp hạng tín dụng thấp, như thể hiện trong hình 3.7.

 

 

 

 

 

 

 

 

 

 

 

 

 

Hình 3.7. Đánh giá tín dụng như là một hàm của độ tuổi và thu nhập

 

Điều gì xảy ra nếu một anh chàng mới đến người là 57 tuổi và người thu nhập $ 37.000? Khả năng nhãn xếp hạng tín dụng của cậu ấy là gì? Nhìn vào hình 3.8. Dựa trên những người khác ở gần anh ấy, nhãn điểm số tín dụng nào bạn nghĩ rằng anh ta có thể được gán? Hãy sử dụng k-NN để làm điều đó tự động.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Hình 3.8. Điều gì xảy ra với chàng trai đó?

Dưới đây là tổng quan của quá trình:

1. Quyết định tương tự của bạn hoặc khoảng cách số liệu.

2. Chia nhãn dữ liệu ban đầu vào dữ liệu haausn luyện và kiểm thử.

3. Chọn một số liệu đánh giá.

4. Chạy k-NN một vài lần, thay đổi k và kiểm tra các biện pháp đánh giá.

5. Tối ưu hóa k bằng cách chọn một với các biện pháp đánh giá tốt nhất.

6. Khi bạn đã chọn k, sử dụng các tập huấn luyện cùng và tạo ra một tập thử nghiệm mới với lứa tuổi của mọi người và thu nhập mà bạn không gãn nhãn, và muốn dự đoán.Trong trường hợp này, tập thử nghiệm mới của bạn chỉ đặt có một hàng, cho 57 tuổi.

Độ tương tự hoặc khoảng cách metrics (Similarity or distance metrics)

Định nghĩa của "sự gần gũi - closeness " và sự tương đồng khác nhau tùy thuộc vào bối cảnh: sự gần gũi trong các mạng xã hội có thể được định nghĩa là số lượng bạn bè chồng chéo.

Vì lợi ích của vấn đề của chúng ta về những gì một người láng ghiềng, chúng ta có thể sử dụng khoảng cách Euclide trên mặt phẳng nếu các biến trên, cùng một tỷ lệ.

Chú ý: Mô hình hóa nguy hiểm phía trước!

Hãy xem xét một ví dụ: Giả sử bạn đo tuổi tính theo năm, thu nhập bằng đô la, và xếp hạng tín dụng như điểm tín dụng thường được đưa ra một số điều như điểm SAT. Sau đó, hai người sẽ được đại diện bởi bộ ba như là (25, 54000, 700) và (35, 76000, 730). Đặc biệt, "khoảng cách" của họ sẽ hoàn toàn bị chi phối bởi sự khác biệt về mức lương của họ.

Mặt khác, nếu bạn thay đổi thang đo lương bằng ngàn đô la, thì họ được đại diện bởi bộ ba (25,54,700) và (35,76,730), mà sẽ nhận được cả ba biến các loại ảnh hưởng tương tự.

Cuối cùng bằng cách co dãn các biến của bạn, hoặc tương đương, trong trường hợp này định nghĩa khái niệm của bạn về khoảng cách theo cách bạn, sẽ có tác dụng tiềm năng rất lớn về đầu ra. Trong thống kê, nó được gọi là “tiên liệu” của bạn.

Khoảng cách Euclide là một cách đi tốt để tách số liệu cho thuộc, tính là giá trị thực và có thể được vẽ trên một mặt phẳng hoặc trong không gian đa chiều. Một số khái niệm khác là:

Cosine Similarity

Ngoài ra có thể được sử dụng giữa hai vectơ giá trị thực,  và sẽ mang lại một giá trị giữa -1 (ngược lại) và 1 (giống hệt nhau) là 0 ở giữa độc lập. Định nghĩa lại

Khoảng cách Jaccard hoặc độ tương tự

Điều này cho phép khoảng cách giữa một tập các đối tượng ví dụ, danh sách bạn bè của Cathy A = {Kahn, Mark, Laura,. . .} và một danh sách bạn bè của Rachel B ={Mladen, Kahn, Mark,. . }. Độ tương tự của 2 tập hợp là: 

Mahalanobis Distance

Khoảng cách Mahalanobis là một cách hữu ích cho việc xác định độ tương tự của một tập các mẫu chưa biết tới một tập các mẫu đã biết. Khác với khoảng cách Euclide, khoảng cách Mahalanobis tính đến các độ tương quan của tập dữ liệu và nó bất biến tỷ lệ, tức là không phụ thuộc vào tỷ lệ của các phép đo. Đây chính là lợi thế của nó so với khoảng cách Euclide.

Khoảng cách Mahalanobis cũng có thể được định nghĩa nhƣ độ đo tính không đồng dạng giữa hai vectơ ngẫu nhiên x và y của cùng phân phối với ma trận đồng biến

Trong đó, S là ma trận hiệp phương sai.

Khoảng cách Hamming

Có thể được sử dụng để tìm khoảng cách giữa hai chuỗi hoặc cặp từ hoặc các trình tự DNA có cùng chiều dài. Khoảng cách giữa “olive” và “ocean” là 4 bởi vì ngoài việc "o" 4 chữ cái khác là khác nhau. Khoảng cách giữa “shoe”và “hose” là 3 bởi vì ngoài chữ cái “e" đứng riêng ra, 3 chữ cái khác là khác nhau. Bạn chỉ cần đi qua mỗi vị trí và kiểm tra xem các chữ cái giống nhau ở vị trí đó, và nếu không, tăng số lượng của bạn bằng 1.

Khoảng cách Manhattan

Đây cũng là một khoảng cách giữa hai giá trị thực vectơ k chiều. Những hình ảnh có trong tâm trí là của một xe taxi phải đi trên đường phố Manhattan, được đặt ra trong một mô hình theo dạng lưới (bạn không thể đi cắt theo đường chéo trên các tòa nhà). Khoảng cách Manhattan, còn được gọi là khoảng cách trong thành phố, là một dạng khoảng cách giữa hai điểm trong không gian Euclid với hệ tọa độ Descartes. Đại lượng này được tính bằng tổng chiều dài của hình chiếu của đường thẳng nối hai điểm này trong hệ trục tọa độ Descartes.

Do đó, khoảng cách  đây i là yếu tố thứ i của mỗi vector. 

Có rất nhiều khoảng cách metric có sẵn cho bạn, tùy thuộc vào loại dữ liệu. Chúng ta có thể tìm kiếm trên Google, khi chúng tôi không chắc chắn bắt đầu từ đâu.

Điều gì xảy ra nếu thuộc tính là một hỗn hợp của các loại dữ liệu? Điều này xảy ra trong trường hợp ví dụ xếp hạng phim: một số đã được tính toán, chẳng hạn như ngân sách và số lượng của các diễn viên, và một là phân loại, thể loại. Nhưng bạn luôn có thể xác định khoảng cách tùy chỉnh metric riêng của bạn.

Ví dụ, bạn có thể nói nếu phim là thể loại tương tự, rằng sẽ phân bố "0" đến khoảng cách của chúng. Nhưng nếu chúng của một thể loại khác nhau, thì sẽ phân bố "10", ở đây bạn chọn giá trị 10 dựa trên thực tế rằng đây là trên quy mô tương tự như ngân sách (triệu USD), mà là ở phạm vi từ 0 đến 100. Bạn có thể làm tương tự với số lượng của các diễn viên. Bạn có thể thực hiện quanh với 10; có lẽ 50 là tốt hơn.

Bạn sẽ muốn để biện minh cho lý do tại sao bạn đang làm cho những sự lựa chọn. Các biện minh có thể là bạn thử các giá trị khác nhau và khi bạn đã thử nghiệm các thuật toán, điều này đã làm cho số liệu đánh giá tốt nhất. Về cơ bản 10, hoặc là một tham số điều chỉnh thứ hai mà đã giới thiệu ở các thuật toán gọi “top” của k, hoặc tham số tiên đoán khi bạn đã đưa vào mô hình, tùy thuộc vào quan điểm của bạn và làm thế nào nó được sử dụng.

Tập huấn luyện và tập kiểm thử

Đối với bất kỳ thuật toán học máy, cách tiếp cận chung là phải có một giai đoạn huấn luyện, trong đó bạn tạo một mô hình và "huấn luyện nó"; và sau đó bạn có một giai đoạn kiểm thử, ở đây bạn sử dụng dữ liệu mới để kiểm tra như thế nào tốt các mô hình.

Đối với k-NN, giai đoạn huấn luyện là đơn giản: nó chỉ đọc trong dữ liệu của bạn với các điểm dữ liệu tín dụng được đánh dấu "cao" hay "thấp". Trong kiểm thử, bạn giả vờ như bạn không biết nhãn đúng sự thật và xem làm thế nào dự đoán tốt nhất bằng cách sử dụng thuật toán k-NN.

Để làm điều này, bạn sẽ cần phải lưu một số dữ liệu sạch từ các dữ liệu tổng thể cho giai đoạn kiểm thử. Thông thường, bạn muốn lưu dữ liệu được lựa chọn ngẫu nhiên, giả sử 20%.

Kết quả R của bạn, có thể trông như thế này:

> head(data)

age income credit

1	69	3	low
2	66	57	low
3	49	79	low
4	49	17	low
5	58	26	High
6	44	71	High

n.points <- 1000 # number of rows in the dataset

sampling.rate <- 0.8

# we need the number of points in the test set to calculate

# the misclassification rate

num.test.set.labels <- n.points * (1 - sampling.rate)

# randomly sample which rows will go in the training set

training <- sample(1:n.points, sampling.rate * n.points, replace=FALSE)

train <- subset(data[training, ], select = c(Age, Income))

# define the training set to be those rows

# the other rows are going into the test set

testing <- setdiff(1:n.points, training)

# define the test set to be the other rows

test <- subset(data[testing, ], select = c(Age, Income))

cl <- data$Credit[training]

# this is the subset of labels for the training set

true.labels <- data$Credit[testing]

# subset of labels for the test set, we're withholding these

Lựa chọn đánh giá metric

Làm thế nào để bạn đánh giá xem liệu mô hình của bạn đã làm một công việc tốt?

Đây không phải là dễ dàng hay phổ quát, bạn có thể quyết định bạn muốn loại bỏ một số loại phân lớp sai nhiều hơn những người khác.

Ví dụ, nếu bạn đang sử dụng một thuật toán phân lớp để dự đoán liệu một người nào đó bị ung thư hay không, bạn sẽ muốn giảm thiểu “âm tính” (chuẩn đóan một người nào đó là không có ung thư khi họ thực sự bị ung thư), vì vậy bạn có thể làm việc với một bác sĩ để điều chỉnh đánh giá số liệu của bạn.

Lưu ý bạn cần phải cẩn thận, vì nếu bạn thực sự muốn âm tính là sai, bạn chỉ có thể nói với mọi người rằng họ có bệnh ung thư. Vì vậy, nó là một sự đánh đổi giữa độ nhạy và độ đặc hiệu, nơi nhạy cảm là ở đây được định nghĩa là xác suất chẩn đoán chính xác bệnh nhân bị bệnh; điểm đặc biệt ở đây là định nghĩa xác suất chẩn đoán chính xác bệnh nhân khỏe là khỏe.

• Độ nhạy cảm (Sensitivity) và đặc trưng (Specificity)

Độ nhạy cảm cũng được gọi là tỷ lệ dương tính đúng (true positive rate) hay còn gọi thu hồi (recall), và thay đổi dựa trên những lĩnh vực học tập mà bạn có, nhưng tất cả đều có nghĩa giống nhau. Và đặc trưng cũng được gọi là tỷ lệ âm tính đúng (true negative rate). Ngoài ra còn có tỷ lệ dương tính sai (false positive rate) và tỷ lệ âm tính sai (false negative), và những tên đặc biệt khác.

Một đánh giá metric có thể sử dụng là recall, được xác định trong Chương 5. Thực tế là một số trong những công thức tương tự có tên gọi khác nhau là do thực tế rằng các ngành học khác nhau đã phát triển những ý tưởng riêng. Vì vậy, precision và recall là số lượng được sử dụng trong lĩnh vực thông tin. Lưu ý, precision không phải là điều tương tự như specificity.

Cuối cùng, chúng tôi có độ chính xác (accuracy), đó là tỷ số của nhãn đúng với tổng số nhãn, và tỷ lệ phân loại sai, mà chỉ là 1- accuracy. Hạn chế tối đa tỷ lệ phân loại sai (misclassification rate) thì chỉ cần tính số lượng để tối đa hóa accuracy.

 

 

Đặt lại tất cả cùng nhau

Bây giờ bạn có một thước đo khoảng cách và số liệu đánh giá.

Đối với mỗi người trong tập kiểm thử của mình, giả vờ như bạn không biết nhãn của mình. Nhìn vào nhãn của ba người láng giềng gần mình, sử dụng các nhãn của đa số phiếu để nhãn cho họ. Bạn sẽ gắn nhãn tất cả các thành viên của tập kiểm thử và sau đó sử dụng các tỷ lệ phân loại sai để xem bạn đã làm như thế nào. Tất cả điều này được thực hiện tự động trong R, chỉ với dòng mã này:

knn (train, test, cl, k=3)

Chọn k

Làm thế nào để bạn chọn k? Đây là một tham số bạn có kiểm soát. Bạn có thể cần phải hiểu dữ liệu của bạn khá tốt để có được một dự đoán tốt, và sau đó bạn có thể thử một vài k khác nhau và xem làm thế nào thay đổi đánh giá của bạn. Vì vậy, bạn sẽ chạy k-nn một vài lần, thay đổi k, và kiểm tra đánh giá số liệu mỗi lần.

• Binary Classe

Khi bạn có các lớp nhị phân như "tín nhiệm cao" hay "thấp tín dụng ", chọn k là một số lẻ có thể là một ý tưởng tốt vì sẽ luôn có một cuộc bỏ phiếu đa số, không có quan hệ. Nếu có một cà vạt, các thuật toán chọn chỉ là ngẫu nhiên.

# we'll loop through and see what the misclassification rate

# is for different values of k

for (k in 1:20) {

print(k)

predicted.labels <- knn(train, test, cl, k)

# We're using the R function knn()

num.incorrect.labels <- sum(predicted.labels != true.labels) misclassification.rate <- num.incorrect.labels /

num.test.set.labels

print(misclassification.rate)

}

Đầu ra trong dạng thức (k, misclassification rate):

k  misclassification.rate 1, 0.28

2, 0.315

3, 0.26

4, 0.255

5, 0.23

6, 0.26

7, 0.25

8, 0.25

9, 0.235

10, 0.24

Vì vậy, chúng ta hãy xét với k = 5 vì nó có tỷ lệ phân loại sai thấp nhất, và bây giờ bạn có thể áp dụng nó cho anh chàng của bạn là người 57 với mức lương 37.000 $. Trong R, nó trông giống như thế này:

> test <- c(57,37)

> knn(train,test,cl, k = 5) [1] low

Các đầu ra bằng đa số phiếu là một số điểm tín dụng thấp khi k = 5.

• Tập kiểm thử ở k-NN

Chú ý chúng tôi sử dụng hàm knn() hai lần và sử dụng nó theo những cách khác nhau. Trong cách thứ nhất, tập kiểm thử là một số dữ liệu, chúng tôi đã sử dụng để đánh giá các mô hình là như thế nào tốt. Trong cách thứ hai, các "thử nghiệm" thiết lập thực sự là một điểm dữ liệu mới mà chúng tôi muốn có một dự đoán. Chúng tôi cũng có thể cho nó nhiều hàng của những người chúng ta muốn dự đoán. Nhưng chú ý rằng R không biết sự khác biệt cho dù những gì bạn đang đặt trong cho tập kiểm thử thực sự là một "thử nghiệm" thiết lập mà bạn biết các nhãn thực sự, hoặc một tập kiểm thử mà bạn không biết và muốn dự đoán.

Các mô hình giả định là gì ?

Trong chương trước, chúng ta đã thảo luận mô hình hóa và mô hình giả định. Vì vậy, các giả định mô hình là những gì ở đây?

Các thuật toán k-NN là một ví dụ về một cách tiếp cận phi tham số. Bạn không có mô hình giả định về sự phân bố dữ liệu tạo cơ bản, và bạn đã không cố gắng để ước lượng tham số nào. Nhưng bạn vẫn có một số giả định, đó là:

• Dữ liệu trong một số không gian đặc trưng, nơi một khái niệm "khoảng cách" có ý nghĩa.

• Dữ liệu huấn luyện đã được dán nhãn hoặc phân thành hai hoặc nhiều lớp.

• Bạn chọn số lượng các láng giềng để sử dụng, k.

• Bạn đang giả định rằng các tính năng quan sát (observed features) và các nhãn (label) được bằng cách nào đó có liên quan. Chúng có thể không, nhưng cuối cùng số liệu đánh giá của bạn sẽ giúp bạn xác định cách tốt thuật toán là ghi nhãn. Bạn có thể muốn thêm nhiều tính năng hơn và kiểm tra cách làm thay đổi các số liệu đánh giá. Sau đó bạn sẽ được điều chỉnh cả các tính năng mà bạn đang sử dụng và k. Nhưng như mọi khi, bạn đang ở trong nguy hiểm ở đây của overfitting.

Cả hai hồi quy tuyến tính và k-NN là những ví dụ của "học giám sát - supervised learning ", ở đây bạn đã quan sát cả x và y, và bạn muốn biết các hàm sẽ mang x với y. Tiếp theo, chúng ta sẽ xem xét một thuật toán mà bạn có thể sử dụng khi bạn không biết câu trả lời là đúng.