Writing

Machine Learning (5) — KNN

K-nearest neighbors and KD-Tree: algorithm principles, the three key elements, and implementation.

Preface: KNN follows a “birds of a feather flock together” idea. Unlike regression algorithms discussed earlier, it has no loss function and predicts by judging how near neighbors are. This article covers the KNN algorithm and KD-Tree.

KNN

  • Algorithm principle: (1) From the training set, get K samples closest to the point to predict; (2) use those K samples to predict the target attribute of the current point; (3) KNN differs mainly in the final decision rule for regression vs. classification. For classification, majority voting is common; for regression, the mean is common.

  • Three elements of KNN: (1) Choice of K: generally pick a small value based on sample distribution, then use cross-validation to choose a suitable final value. A small K uses a smaller neighborhood, reducing training error but making the model more complex and prone to overfitting. A large K uses a larger neighborhood, increasing training error but simplifying the model and risking underfitting. (2) Distance metric: usually Euclidean distance. Code:

def point_Distance(x1,y1,x2,y2):
    d = math.sqrt(math.pow((x1-x2),2)+math.pow((y1-y2),2))
    return d
a_d = point_Distance(18,90,3,104)
print(a_d)

(3) Decision rule: in classification, majority voting or weighted majority voting; in regression, mean or weighted mean. Weights are often inversely proportional to distance.

image

Hand-written KNN:

import math
import csv
import operator
import random
def loadDataset(fileName,split,trainingSet=[],textSet=[]):
    with open(fileName, "r") as f:
        reader = csv.reader(f)
        data = list(reader)
        for x in range(len(data) - 1):
            for y in range(4):
                data[x][y] = float(data[x][y])
            if random.random() < split:
                trainingSet.append(data[x])
            else:
                textSet.append(data[x])
        return trainingSet,textSet
        # print(trainingSet)
        # print(textSet)
# trainingSet,textSet=loadDataset("irisdata.csv",0.7)
# print(trainingSet)
# print(textSet)

def euclideanDistence(instance1,instence2,length):
    distance = 0
    for x in range(length):
        distance += pow(instance1[x]-instence2[x],2)
    return math.sqrt(distance)
# s = euclideanDistence([1,2,3],[4,5,6],3)
# print(s)

'''
去测试集一个数据，放到训练集中，给定一个k，返回k个训练集（这k个训练集的值就是离这个测试集最近的k个点）
'''
def getNeighbors(trainingSet,textInstance,k):
    distane = []
    length = len(textInstance)-1
    for x in range(len(trainingSet)):
        dist = euclideanDistence(trainingSet[x], textInstance, length)
        distane.append((trainingSet[x],dist))#append只能传一个参数，用括号括起来
    distane1 = sorted(distane,key=operator.itemgetter(1))#排序
    neighbors = []
    for x in range(k):
        neighbors.append(distane1[x][0])
    return neighbors
    # print(neighbors)
'''
对返回的结果进行分类累加
对返回的最近的数进行判断，是不是和textinstance相符
'''
def getResponse(neighbors):
    classVators = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if response in classVators:
            classVators[response] +=1
        else:
            classVators[response]=1
    sortVators = sorted(classVators.items(),key=operator.itemgetter(1),reverse=True)
    # print(classVators)
    return sortVators[0][0]
'''
计算正确率
'''
def getAccuracy(textSet,predictions):
    corret = 0
    for x in range(len(textSet)):
        if textSet[x][-1] == predictions[x]:
            corret += 1
    return (corret/len(textSet))*100
#判断正确率的主函数
def main1():
    trainingSet,textSet=loadDataset("irisdata.csv",0.8)
    predictions = []
    for x in range(len(textSet)):
        neighbors=getNeighbors(trainingSet,textSet[x],6)
        sortVators = getResponse(neighbors)
        predictions.append(sortVators)
    re = getAccuracy(textSet,predictions)
    print(re)
main1()

Using scikit-learn is of course simpler.

KD Tree

KD Tree is a fast, convenient structure for nearest-neighbor search in KNN. With few samples, brute force (computing distance to all samples) works. With many samples, computing all distances is expensive, so KD Tree speeds things up.

  • Building a KD Tree: From n dimensions of m samples, compute variance for each dimension; use the dimension k with largest variance as the root. For that feature, use the median as the split; samples below go to the left subtree, those above or equal to the right. Repeat on subtrees the same way. As shown: image

  • Nearest-neighbor search image Finally, some scikit-learn parameter meanings: image