Примечания к машинному обучению 1 (алгоритм K-ближайшего соседа)

Жизнь слишком коротка, я использую Python

Алгоритм K-ближайшего соседа: Проще говоря, алгоритм K-ближайших соседей заключается в использовании метода измерения расстояния между различными собственными значениями для классификации

Преимущества: высокая точность, нечувствительность к выбросам, отсутствие допущений при вводе данных.
Недостатки: высокая вычислительная сложность, высокая пространственная сложность.
Область применения: числовая, номинальная

Принцип работы:

Существует выборочный набор данных, также известный как набор обучающей выборки, и каждые данные в выборочном наборе имеют метку, то есть мы знаем соответствие между каждыми данными в выборочном наборе и категорией, к которой он принадлежит. После ввода новых данных без меток каждый признак новых данных сравнивается с признаками, соответствующими данным в выборке, а затем алгоритм извлекает классификационные метки данных (ближайшие соседи) с наиболее похожими признаками в выборке. набор. Как правило, мы выбираем только верхние K наиболее похожих данных в выборке, которая является источником K в алгоритме K ближайших соседей, обычно K является целым числом, не превышающим 20. Наконец, классификация с наибольшим количеством вхождений среди K наиболее похожих данных выбирается в качестве классификации новых данных.

Общий поток алгоритма K-ближайшего соседа:

Сбор данных: можно использовать любой метод.
Подготовьте данные: числовые значения, необходимые для расчета расстояния, желательно в структурированном формате данных.
Анализ данных: можно использовать любой метод.
Обучите алгоритм: этот шаг не применяется к алгоритму K-ближайших соседей.
Алгоритм тестирования: вычислить частоту ошибок.
Использование алгоритма: во-первых, вам нужно ввести выборочные данные и структурированные выходные результаты, затем запустить алгоритм K-ближайших соседей, чтобы определить, к какой классификации принадлежат входные данные, и, наконец, применить рассчитанную классификацию для выполнения последующей обработки.

Реализация алгоритма классификации KNN — псевдокод

Сделайте следующее по очереди для каждой точки в наборе данных с неизвестными атрибутами класса:

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

Вычислите формулу расстояния между двумя точками вектора — формула евклидова расстояния:

Например: расстояние между точками (0, 0) и (1, 2) рассчитывается как:

sqrt((1-0)**2+(2-0)**2)

Код:

import numpy as np
import operator
"""
def CreateDataSet():
    group=np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels=['A','A','B','B']
    return group,labels
print(CreateDataSet())
"""
"""
inX--用于分类的输入向量
dataSet--输入的训练样本集
labels--标签向量
k--用于选择最近邻居的数目
其中标签向量的元素数目和矩阵dataSet的行数相同
"""
def classify(inX,dataSet,labels,k):
    dataSetSize=dataSet.shape[0]    #获得训练样本集的行数

    #将输入向量在列方向重复一次，在行方向上dataSize次，并与训练样本集dataSet相减
    diffMat=np.tile(inX,(dataSetSize,1))-dataSet
    print("diffMat:")
    print(diffMat)
    #将相减后的集合进行平方运算
    sqDiffMat=diffMat**2
    print("sqDiffMat:")
    print(sqDiffMat)
    #对平方后的集合进行相加运算--按行相加
    sqDistances=sqDiffMat.sum(axis=1)
    print("sqDistances:")
    print(sqDistances)
    #对相加后的数据开平方，得到输入向量与每个训练样本集之间的距离值
    distances=np.sqrt(sqDistances)
    print("distances")
    print(distances)
    #返回数组从小到大的索引值--排序
    sortedDistIndicies=np.argsort(distances)
    print("sortedDistIndicies")
    print(sortedDistIndicies)
    classCount={}

    for i in range(k):
        voteIlabel=labels[sortedDistIndicies[i]]
        print("voteIlabel"+str(i))
        print(voteIlabel)
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
        print("classCount"+str(i))
        print(classCount)
    sortedClassCount=sorted(classCount.items(),
                            key=operator.itemgetter(1),reverse=True)
    print("sortedClassCount:")
    print(sortedClassCount)
    return sortedClassCount[0][0]

if __name__=='__main__':
    #训练样本集
    group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])

    #标签向量
    labels = ['A', 'A', 'B', 'B']

    #输入向量
    inX=[0,0]

    #用于选择最近邻居的数目
    k=3
    result=classify(inX,group,labels,k)
    print(result)


"""
输出值：
diffMat:
[[-1.  -1.1]
 [-1.  -1. ]
 [ 0.   0. ]
 [ 0.  -0.1]]
sqDiffMat:
[[ 1.    1.21]
 [ 1.    1.  ]
 [ 0.    0.  ]
 [ 0.    0.01]]
sqDistances:
[ 2.21  2.    0.    0.01]
distances
[ 1.48660687  1.41421356  0.          0.1       ]
sortedDistIndicies
[2 3 1 0]
voteIlabel0
B
classCount0
{'B': 1}
voteIlabel1
B
classCount1
{'B': 2}
voteIlabel2
A
classCount2
{'B': 2, 'A': 1}
sortedClassCount:
[('B', 2), ('A', 1)]
B

Process finished with exit code 0
"""

Результаты теста:

Введите [0,0], после проверки возвращаемый результат равен B, то есть входной вектор [0,0] классифицируется как класс B алгоритмом K-ближайшего соседа

Пример: использование алгоритма K-ближайших соседей для улучшения подбора партнеров на сайтах знакомств

Собрать данные: предоставить текстовый файл
Подготовка данных: разбор текстовых файлов с помощью Python
Анализ данных: рисование 2D-графиков диффузии с помощью Matplotlib
Алгоритм обучения: этот шаг не применяется к алгоритму K-ближайших соседей.
Алгоритм тестирования: использовать часть данных, предоставленных Еленой, в качестве тестового образца.
Отличие тестовой выборки от нетестовой состоит в том, что тестовая выборка — это уже классифицированные данные, и если прогнозируемая классификация отличается от фактического класса, она помечается как ошибка.
Используйте алгоритм: создайте простую программу командной строки, а затем вы можете ввести некоторые характерные данные, чтобы определить, является ли другая сторона вашим любимым типом

Подготовка данных: Анализ данных из текстовых файлов

Особенности текстовых образцов данных:

Годовые мили для часто летающих пассажиров
% времени, проведенного за видеоиграми
Литров мороженого, потребляемых в неделю

Парсер для преобразования текстовых записей в данные numpy:

def file2matrix(filename):
    # 打开文件
    fr = open(filename, 'r', encoding='utf-8')

    # 按行读取数据
    arrayOLines = fr.readlines()

    # 获取数据的行数
    numberOfLines = len(arrayOLines)
    # 创建以0填充的矩阵
    returnMat = np.zeros((numberOfLines, 3))
    print(returnMat)
    classLabelVector = []
    index = 0
    for line in arrayOLines:
        print(line)
        # 截取掉所有回车字符
        line = line.strip()
        print(line)
        # 以'\t'将line分割成一个元素列表
        listFromLine = line.split('\t')
        # 选取前三个元素，存储到特征矩阵中
        returnMat[index, :] = listFromLine[0:3]
        # 选取最后一个元素存储到标签向量中
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector
datingDataMat,datingLabels=file2matrix('D:\liuguojiang_Python\city_58\city_58\datingTestSet2.txt')
fig=plt.figure()
plt.title('K-')
plt.xlabel('fly')
plt.ylabel('consume')
ax=fig.add_subplot(111)

ax.scatter(datingDataMat[:,0],datingDataMat[:,1],
           15.0*np.array(datingLabels),15.0*np.array(datingLabels))
plt.show()

Специальное примечание: файлы ресурсов в коде можно скачать здесь:LiuGuoJiang/machinelearninginaction

Разобрать текстовые данные и отобразить их на точечной диаграмме:

Подготовка данных: нормализованные значения

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

newValue=(oldValue-min)/(max-min)

где min и max — наименьшее и наибольшее собственные значения в наборе данных соответственно.

Нормализованная функция собственного значения:

def autoNorm(dataSet):
    #选取列的最小值
    minVals=dataSet.min(0)
    #选取列的最大值
    maxVals=dataSet.max(0)
    #列的最大值与最小值做减法
    ranges=maxVals-minVals
    #
    normDataSet=np.zeros([dataSet.shape[0],dataSet.shape[1]])
    print(normDataSet)
    #取出dataSet的行数
    m=dataSet.shape[0]
    #np.tile(minVals,(m,1))将minVals在 列上重复一次，在行上重复m次
    normDataSet=dataSet-np.tile(minVals,(m,1))  #（oldValue-min）
    normDataSet=normDataSet/np.tile(ranges,(m,1))   #(oldValue-min)/(max-min)
    return normDataSet,ranges,minVals

normDataSet,ranges,minVals=autoNorm(datingDataMat)
print(normDataSet)

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

Код теста классификатора:

def datingClassUnitTest():
    hoRatio=0.10
    datingDataMat, datingLabels = file2matrix('D:\liuguojiang_Python\city_58\city_58\datingTestSet2.txt')
    print(datingDataMat)
    normDataSet, ranges, minVals = autoNorm(datingDataMat)
    print(normDataSet)
    m=normDataSet.shape[0]
    numTestVecs=int(m*hoRatio)
    print("numTestVecs")
    print(numTestVecs)
    errorCount=0.0
    for i in range(numTestVecs):
        classifierResult=classify(normDataSet[i,:],normDataSet[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        print("the classfier came back with:{},the real answer is:{}".format(classifierResult,datingLabels[i]))
        if (classifierResult!=datingLabels[i]):errorCount+=1.0
    print("the total error rate is:{}".format(errorCount/float(numTestVecs)))


the classfier came back with:3,the real answer is:3
the classfier came back with:2,the real answer is:2
the classfier came back with:1,the real answer is:1
.........
the classfier came back with:1,the real answer is:1
the classfier came back with:3,the real answer is:3
the classfier came back with:3,the real answer is:3
the classfier came back with:2,the real answer is:2
the classfier came back with:1,the real answer is:1
the classfier came back with:3,the real answer is:1
the total error rate is:0.05

Частота ошибок классификатора, обрабатывающего набор данных, составляет 5%, что означает, что классификатор может помочь объекту определить классификацию.

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

def classifyPerson():
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTats = float(input( \
        "percentage of time spent playing video games?"))
    ffMiles = float(input("frequent flier miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2matrix('D:\liuguojiang_Python\city_58\city_58\datingTestSet2.txt')
    normDataSet, ranges, minVals = autoNorm(datingDataMat)
    inArr = np.array([ffMiles, percentTats, iceCream, ])
    classifierResult = classify((inArr - \
                                  minVals) / ranges, normDataSet, datingLabels, 3)
    print("You will probably like this person: {}".format(resultList[classifierResult - 1]))
if __name__=='__main__':
    classifyPerson()

"""
return:
percentage of time spent playing video games?10
frequent flier miles earned per year?10000
liters of ice cream consumed per year?0.5
You will probably like this person: in small doses
"""

Суммировать:

Задайте программу алгоритма K ближайших соседей.
Определяет функции для преобразования текстовых наборов данных в двумерные массивы для упрощения обработки.
Для того, чтобы исключить влияние определенного значения признака на оценку результата, определена нормированная числовая функция, формула: (старое значение-мин)/(макс-мин)
Определите функцию алгоритма тестирования, чтобы проверить, соответствует ли частота ошибок классификатора требованиям использования.
Определите код, который может ввести пользователь, введите входной вектор и используйте его для определения классификации.