纯python实现机器学习之kNN算法示例

首先我们需要清楚kNN算法的基本思想。kNN算法是一种基于实例的有监督学习算法，可以用于分类和回归问题。对于一个新的未标记数据，该算法会根据其与训练集中数据的距离，找到距离该点最近的k个点，然后根据这k个点的标签或者值来对该点进行分类或回归。

以下是具体实现步骤：

准备数据

kNN算法需要一个已经标记好的训练数据集。这里我们以Iris花卉数据集为例。我们先把数据集中的数据提取出来，然后将其随机分为训练集和测试集两部分。

import random

def load_data(filename, split, training_set=[], test_set=[]):
    with open(filename, 'r') as f:
        lines = f.readlines()
        for i in range(len(lines)):
            line = lines[i].strip()
            if len(line) == 0:
                continue
            parts = line.split(',')
            for j in range(4):
                parts[j] = float(parts[j])
            if random.random() < split:
                training_set.append(parts)
            else:
                test_set.append(parts)

training_set = []
test_set = []
load_data('iris.data', 0.66, training_set, test_set)
print(f'Training set: {len(training_set)}')
print(f'Test set: {len(test_set)}')

我们使用了一个load_data函数，将数据集进行加载，并将其分为训练集和测试集。split参数是指将数据随机分为训练集和测试集的比例。这里我们将数据集分为66%的训练数据和33%的测试数据。

计算距离

接下来我们需要根据测试数据和训练数据计算距离。在这里我们使用欧几里得距离来计算距离，其公式为：

$distance = \sqrt{\sum{(a_i - b_i)^2}}$

import math

def euclidean_distance(instance1, instance2, length):
    distance = 0
    for i in range(length):
        distance += pow((instance1[i] - instance2[i]), 2)
    return math.sqrt(distance)

我们使用了一个euclidean_distance函数，该函数接受两个实例instance1和instance2，以及两个实例的长度length作为输入参数，然后使用欧几里得距离公式计算出它们之间的距离。

找到最近的k个点

接下来，我们需要根据测试数据和训练数据计算距离，并找到测试数据最近的k个训练数据点。

import operator

def get_nearest_neighbors(training_set, test_instance, k):
    distances = []
    length = len(test_instance) - 1
    for i in range(len(training_set)):
        dist = euclidean_distance(test_instance, training_set[i], length)
        distances.append((training_set[i], dist))
    distances.sort(key=operator.itemgetter(1))
    neighbors = []
    for i in range(k):
        neighbors.append(distances[i][0])
    return neighbors

在该函数中，我们首先计算每个训练数据点与测试点之间的距离。然后对这些距离进行排序，并选取前k个距离最近的训练数据点作为测试点的邻居。

注：如果有数据距离相同，我们可以按照随机的顺序选择邻居，或者选择距离相同的所有邻居。

预测测试数据的分类

现在我们已经得到了测试数据的k个邻居。接下来我们可以根据这k个邻居的标签来预测出测试点的分类。

def predict_class(neighbors):
    class_votes = {}
    for i in range(len(neighbors)):
        label = neighbors[i][-1]
        if label in class_votes:
            class_votes[label] += 1
        else:
            class_votes[label] = 1
    sorted_votes = sorted(class_votes.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_votes[0][0]

在该函数中，我们遍历测试点的邻居，并统计每个标签出现的次数。然后我们按照标签出现次数从高到低排序，并选择出现次数最高的标签作为测试点的预测分类。

现在我们已经完成了kNN模型的构建。接下来我们可以对测试集中的每个测试数据点进行预测，并计算模型的准确率。以下是完整示例代码：

# kNN algorithm
import random
import math
import operator

def load_data(filename, split, training_set=[], test_set=[]):
    with open(filename, 'r') as f:
        lines = f.readlines()
        for i in range(len(lines)):
            line = lines[i].strip()
            if len(line) == 0:
                continue
            parts = line.split(',')
            for j in range(4):
                parts[j] = float(parts[j])
            if random.random() < split:
                training_set.append(parts)
            else:
                test_set.append(parts)

def euclidean_distance(instance1, instance2, length):
    distance = 0
    for i in range(length):
        distance += pow((instance1[i] - instance2[i]), 2)
    return math.sqrt(distance)

def get_nearest_neighbors(training_set, test_instance, k):
    distances = []
    length = len(test_instance) - 1
    for i in range(len(training_set)):
        dist = euclidean_distance(test_instance, training_set[i], length)
        distances.append((training_set[i], dist))
    distances.sort(key=operator.itemgetter(1))
    neighbors = []
    for i in range(k):
        neighbors.append(distances[i][0])
    return neighbors

def predict_class(neighbors):
    class_votes = {}
    for i in range(len(neighbors)):
        label = neighbors[i][-1]
        if label in class_votes:
            class_votes[label] += 1
        else:
            class_votes[label] = 1
    sorted_votes = sorted(class_votes.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_votes[0][0]

def get_accuracy(test_set, predictions):
    correct = 0
    for i in range(len(test_set)):
        if test_set[i][-1] == predictions[i]:
            correct += 1
    return (correct/float(len(test_set))) * 100.0

def main():
    # prepare data
    training_set = []
    test_set = []
    split = 0.66
    load_data('iris.data', split, training_set, test_set)
    print(f'Training set: {len(training_set)}')
    print(f'Test set: {len(test_set)}')
    # generate predictions
    predictions = []
    k = 3
    for i in range(len(test_set)):
        neighbors = get_nearest_neighbors(training_set, test_set[i], k)
        result = predict_class(neighbors)
        predictions.append(result)
        print(f'prediction: {result}, actual: {test_set[i][-1]}')
    accuracy = get_accuracy(test_set, predictions)
    print(f'Accuracy: {accuracy}%')

main()

当运行以上代码时，它会首先输出训练数据集和测试数据集的信息，然后打印出每个测试数据点的预测分类和实际分类，并计算出kNN模型的准确率。

以上就是使用纯Python实现kNN算法的完整攻略。如果你想了解更多有关kNN算法的实现细节，以及如何将其应用于其他数据集，请参考一些开源的机器学习库或教程。