Алгоритм машинного обучения kNN (реализация на чистом питоне)

В предыдущих статьях кратко были представлены линейная регрессия, логистическая регрессия и байесовская классификация, и они были реализованы в Python. В этом посте представлен более простой алгоритм knn, k-ближайших соседей (kNN, k-NearestNeighbor).k-近邻算法（kNN，k-NearestNeighbor），是最简单的机器学习分类算法之一，其核心思想在于用距离目标最近的k个样本数据的分类来代表目标的分类（这k个样本数据和目标数据最为相似）。

принцип

Основная идея алгоритма kNN состоит в том, чтобы представить классификацию целевых данных с помощью k выборочных данных с ближайшим расстоянием (различные способы измерения расстояния).

В частности, естьобучающая выборка, каждая выборка содержит функции данных и значение категории, к которой она принадлежит. Введите новые данные, сравните данные с каждой выборкой в наборе обучающей выборки и найдите k ближайших расстояний Среди k данных классификация с наибольшим количеством вхождений может использоваться как классификация новых данных.

Как показано выше: Нужно определить, какой формы зеленый цвет. Когда k равно 3, он принадлежит треугольнику. Когда k равно 5, оно принадлежит квадрату. Таким образом, этот метод имеет следующие характеристики:

Обучение под наблюдением: набор обучающих образцов содержит информацию о классификации.
Алгоритм прост и легок для понимания и реализации
На результат влияет значение k, которое обычно не превышает 20.
Объем вычислений велик, и необходимо рассчитать расстояние до каждого образца в наборе образцов.
Несбалансированная обучающая выборка приводит к неточным результатам

Затем сделайте простую реализацию с oython и попробуйте сопоставить ее с сайтами знакомств.

Простая реализация питона

def classify(inX, dataSet, labels, k):
    """
    定义knn算法分类器函数
    :param inX: 测试数据
    :param dataSet: 训练数据
    :param labels: 分类类别
    :param k: k值
    :return: 所属分类
    """

    dataSetSize = dataSet.shape[0]  #shape（m, n）m列n个特征
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5  #欧式距离
    sortedDistIndicies = distances.argsort()  #排序并返回index

    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #default 0

    sortedClassCount = sorted(classCount.items(), key=lambda d:d[1], reverse=True)
    return sortedClassCount[0][0]

Шаги алгоритма подробно описаны выше.Приведенный выше расчет является матричной операцией, а следующая функция является алгебраической операцией.

def classify_two(inX, dataSet, labels, k):
    m, n = dataSet.shape   # shape（m, n）m列n个特征
    # 计算测试数据到每个点的欧式距离
    distances = []
    for i in range(m):
        sum = 0
        for j in range(n):
            sum += (inX[j] - dataSet[i][j]) ** 2
        distances.append(sum ** 0.5)

    sortDist = sorted(distances)

    # k 个最近的值所属的类别
    classCount = {}
    for i in range(k):
        voteLabel = labels[ distances.index(sortDist[i])]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 # 0:map default
    sortedClass = sorted(classCount.items(), key=lambda d:d[1], reverse=True)
    return sortedClass[0][0]

С помощью приведенного выше классификатора проще всего предсказать следующий эксперимент:

def createDataSet():
    group = np.array([[1, 1.1], [1, 1], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

Выше приведен простой набор обучающих образцов.

if __name__ == '__main__':
    dataSet, labels = createDataSet()
    r = classify_two([0, 0.2], dataSet, labels, 3)
    print(r)

Выполните приведенную выше функцию: вы можете видеть, что вывод B, [0,0.2] должен быть отнесен к классу b.

Выше приведен простейший классификатор kNN, а ниже приведен пример.

kNN используется для оценки популярности людей на сайтах знакомств.

Некоторые данные в наборе обучающей выборки следующие:

40920	8.326976	0.953952	3
14488	7.153469	1.673904	2
26052	1.441871	0.805124	1
75136	13.147394	0.428964	1
38344	1.669788	0.134296	1

В первом столбце показано количество миль для часто летающих пассажиров, заработанных каждый год, во втором столбце указан процент времени, проведенного за видеоиграми, а в третьем столбце указано количество литров мороженого, потребляемых в неделю. В четвертом столбце представлены результаты классификации, 1, 2 и 3 — неприязнь, среднее обаяние и очень привлекательная, соответственно.

Преобразуйте данные в numpy.

# 文本转换成numpy
def file2matrix(filepath="datingSet.csv"):
    dataSet = np.loadtxt(filepath)
    returnMat = dataSet[:, 0:-1]
    classlabelVector = dataSet[:, -1:]
    return returnMat, classlabelVector

Во-первых, имейте представление о данных, знайте, какие функции влияют на классификацию, и выполняйте визуальный анализ данных.

# 2， 3列数据进行分析
def show_2_3_fig():
    data, cls = file2matrix()
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(data[:, 1], data[: ,2], c=cls)
    plt.xlabel("playing game")
    plt.ylabel("Icm Cream")
    plt.show()

Как видно из приведенного выше рисунка, четкой классификации нет.

Видно, что разные люди четко дифференцированы по своим характеристикам. Следовательно, алгоритм kNN можно использовать для классификации и предсказания.

Поскольку сравнение расстояний будет использоваться позже, большее влияние оказывают предыдущие данные, такие как разрыв между пробегом самолета и количеством мороженого. Поэтому данные должны бытьнормализация.

# 数据归一化
def autoNorm(dataSet):
    minVal = dataSet.min(0)
    maxVal = dataSet.max(0)
    ranges = maxVal - minVal

    normDataSet = np.zeros(dataSet.shape)
    m, n = dataSet.shape  # 行， 特征
    normDataSet = dataSet - minVal
    normDataSet = normDataSet / ranges
    return normDataSet, ranges, minVal

Измерьте точность алгоритма Алгоритм knn можно измерить по правильной скорости или частоте ошибок. Уровень ошибок 0 указывает на хорошую классификацию. Таким образом, 10% обучающих выборок можно использовать для тестирования, а 90% — для обучения.

# 定义测试算法的函数
def datingClassTest(h=0.1):
    hoRatio = h
    datingDataMat, datingLabels = file2matrix()
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m, n = normMat.shape
    numTestVecs = int(m * hoRatio)  #测试数据行数
    errorCount = 0  # 错误分类数


    # 用前10%的数据做测试
    for i in range(numTestVecs):
        classifierResult = classify(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m],  3)
        # print('the classifier came back with: %d,the real answer is: %d' % (int(classifierResult), int(datingLabels[i])))
        if classifierResult != datingLabels[i]:
            errorCount += 1
    print("the total error rate is: %f" % (errorCount / float(numTestVecs)))

Отрегулируйте различные тестовые шкалы и сравните результаты.

Используйте knn для предсказания. Имея в наличии обучающие выборки и классификаторы, можно делать прогнозы на основе новых данных. Смоделируйте данные и сделайте прогнозы следующим образом:

# 简单进行预测
def classifypersion():
    resultList = ["none", 'not at all','in small doses','in large doses']
    # 模拟数据
    ffmiles = 15360
    playing_game = 8.545204
    ice_name = 1.340429

    datingDataMat, datingLabels = file2matrix()
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = np.array([ffmiles, playing_game, ice_name])
    # 预测数据归一化
    inArr = (inArr - minVals) / ranges
    classifierResult = classify(inArr, normMat, datingLabels, 3)
    print(resultList[int(classifierResult)])

Вы можете увидеть основную категорию, к которой он принадлежит.

Для получения полных кодов и данных см.:
github:kNN

Суммировать

kNN
контролируемое обучение
визуализация данных
Нормализация данных, не влияет на расчет