Недавно я читал книгу «Машинное обучение на практике», потому что хотел глубоко разобраться в алгоритмах машинного обучения, и я хотел изучить python, поэтому выбрал эту книгу для обучения по рекомендации друга.
1. Обзор алгоритма K-ближайших соседей (KNN)
Самый простой и элементарный классификатор состоит в том, чтобы записать все категории, соответствующие обучающим данным.Когда атрибуты тестового объекта точно совпадают с атрибутами обучающего объекта, его можно классифицировать. Но как возможно, чтобы все тестовые объекты находили в точности соответствующие им обучающие объекты?Во-вторых, существует проблема, связанная с тем, что тестовый объект сопоставляется с несколькими обучающими объектами одновременно, в результате чего обучающий объект делится на несколько классов. Исходя из этих проблем и производится как раз КНН.
KNN классифицируется путем измерения расстояния между различными значениями признаков. Его идея такова: если большинство из k наиболее похожих выборок в пространстве признаков (то есть ближайших соседей в пространстве признаков) принадлежат к определенной категории, то выборка также принадлежит к этой категории, где K обычно не больше An целое число 20. В алгоритме KNN выбранными соседями являются все правильно классифицированные объекты. В решении о классификации этот метод определяет только категорию пробы, подлежащей классификации, в соответствии с категорией ближайшей одной или нескольких проб.
Поясним на простом примере: Как показано на рисунке ниже, к какому классу должен быть отнесен зеленый кружок, красный треугольник или синий квадрат? Если K=3, поскольку пропорция красных треугольников равна 2/3, зеленому кружку будет присвоен класс красных треугольников, если K=5, так как пропорция синих четырехугольников равна 3/5, будет присвоен зеленый кружок класс синих квадов Квадратный класс.
Это также показывает, что результат алгоритма KNN в значительной степени зависит от выбора K.
В KNN, вычисляя расстояние между объектами как показатель несходства между объектами, можно избежать проблемы соответствия между объектами.Здесь расстояние обычно использует евклидово расстояние или манхэттенское расстояние:
В то же время KNN принимает решения на основе доминирующей категории среди k объектов, а не решения по одной категории объектов. Эти два момента являются преимуществами алгоритма KNN.
Далее резюмируется идея алгоритма KNN: когда известны данные и метки в обучающем наборе, ввести тестовые данные, сравнить признаки тестовых данных с соответствующими признаками в обучающем наборе и найти наиболее аналогичный в обучающем наборе.Для первых данных K категория, соответствующая тестовым данным, является категорией с наибольшим количеством вхождений среди данных K. Описание алгоритма выглядит следующим образом:
1) Рассчитать расстояние между тестовыми данными и каждыми обучающими данными;
2) Сортировка по возрастанию отношения расстояния;
3) Выберите K точек с наименьшим расстоянием;
4) Определить частоту встречаемости категории, к которой относятся первые K баллов;
5) Верните категорию с наибольшей частотой в верхних K баллах в качестве предсказанной классификации тестовых данных.
Две реализации .python
Прежде всего, следует отметить, что я использую python3.4.3, и некоторые варианты использования отличаются от 2.7.
Создайте файл KNN.py, чтобы проверить выполнимость алгоритма, следующим образом:
#coding:utf-8
from numpy import *
import operator
##给出训练数据以及对应的类别
def createDataSet():
group = array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]])
labels = ['A','A','B','B']
return group,labels
###通过KNN进行分类
def classify(input,dataSe t,label,k):
dataSize = dataSet.shape[0]
####计算欧式距离
diff = tile(input,(dataSize,1)) - dataSet
sqdiff = diff ** 2
squareDist = sum(sqdiff,axis = 1)###行向量分别相加，从而得到新的一个行向量
dist = squareDist ** 0.5
##对距离进行排序
sortedDistIndex = argsort(dist)##argsort()根据元素的值从大到小对元素进行排序，返回下标
classCount={}
for i in range(k):
voteLabel = label[sortedDistIndex[i]]
###对选取的K个样本所属的类别个数进行统计
classCount[voteLabel] = classCount.get(voteLabel,0) + 1
###选取出现的类别次数最多的类别
maxCount = 0
for key,value in classCount.items():
if value > maxCount:
maxCount = value
classes = key
return classes
Далее введите следующий код в окно командной строки:
#-*-coding:utf-8 -*-
import sys
sys.path.append("...文件路径...")
import KNN
from numpy import *
dataSet,labels = KNN.createDataSet()
input = array([1.1,0.3])
K = 3
output = KNN.classify(input,dataSet,labels,K)
print("测试数据为:",input,"分类结果为：",output)Результат после возврата каретки:
Данные испытаний: [ 1.1 0.3] Классификация: A
Ответ соответствует нашим ожиданиям: чтобы доказать точность алгоритма, его необходимо проверить, решая сложные задачи, которые будут объяснены позже.
Это первый раз, когда я скомпилировал небольшую программу на python, и она неизбежно столкнется с различными проблемами.В процессе программирования и отладки я столкнулся со следующими проблемами:
1 Возникла проблема с импортом пути к файлу .py, поэтому нужно добавить в начало следующий код:
- импорт системы
sys.path.append("путь к файлу"), поэтому не будет проблем с неправильным путем;
2 Когда python подскажет, что есть проблема с кодом, обязательно вовремя исправьте его.После исправления сохраните, а затем выполните командную строку.Это отличается от MATLAB.Поэтому в python лучше всего набирать код в командной строке раздел за разделом Verify;
3 При вызове файла имя функции должно быть написано правильно, иначе будет выглядеть: объект 'module' не имеет атрибута 'creatDataSet';
4 'int' объект не имеет атрибута 'kclassify', причина этой проблемы в том, что я сказал ранее, что файл сохраняется как k.py при выполнении
output = K.classify(input,dataSet,labels,K)这一句就会出错。根据函数式编程的思想，每个函数都可以看为是一个变量而将K赋值后，调用k.py时就会出现问题。
三 MATLAB实现
之前一直在用MATLAB做聚类算法的一些优化，其次就是数模的一些常用算法，对于别的算法，还真是没有上手编过，基础还在，思想还在，当然要动手编一下，也是不希望在学python的同时对MATLAB逐渐陌生吧，走走停停，停很重要。
首先，建立KNN.m文件，如下：
%% KNN
clear all
clc
%% data
trainData = [1.0,2.0;1.2,0.1;0.1,1.4;0.3,3.5];
trainClass = [1,1,2,2];
testData = [0.5,2.3];
k = 3;
%% distance
row = size(trainData,1);
col = size(trainData,2);
test = repmat(testData,row,1);
dis = zeros(1,row);
for i = 1:row
diff = 0;
for j = 1:col
diff = diff + (test(i,j) - trainData(i,j)).^2;
end
dis(1,i) = diff.^0.5;
end
%% sort
jointDis = [dis;trainClass];
sortDis= sortrows(jointDis');
sortDisClass = sortDis';
%% find
class = sort(2:1:k);
member = unique(class);
num = size(member);
max = 0;
for i = 1:num
count = find(class == member(i));
if count > max
max = count;
label = member(i);
end
end
disp('最终的分类结果为：');
fprintf('%d\n',label) Результат после запуска таков, что окончательный результат классификации: 2. как ожидаемый результат.
Три реальных боя
Раньше проводилась простая проверка KNN.Сегодня мы используем KNN для улучшения эффекта сайтов знакомств.Лично я понимаю, что эта проблема может трансформироваться и в другие рекомендации, например, рекомендации различных сайтов для удовлетворения предпочтений клиентов Конечно, сегодня функционал этого примера тоже очень ограничен.
Здесь по собранным человеком данным датирования, по основным характеристикам выборки и полученной классификации классифицируются некоторые неизвестные категории данных, что примерно одно и то же.
Я использую python 3.4.3, сначала создайте файл, например date.py, конкретный код выглядит следующим образом:
#coding:utf-8
from numpy import *
import operator
from collections import Counter
import matplotlib
import matplotlib.pyplot as plt
###导入特征数据
def file2matrix(filename):
fr = open(filename)
contain = fr.readlines()###读取文件的所有内容
count = len(contain)
returnMat = zeros((count,3))
classLabelVector = []
index = 0
for line in contain:
line = line.strip() ###截取所有的回车字符
listFromLine = line.split('\t')
returnMat[index,:] = listFromLine[0:3]###选取前三个元素，存储在特征矩阵中
classLabelVector.append(listFromLine[-1])###将列表的最后一列存储到向量classLabelVector中
index += 1
##将列表的最后一列由字符串转化为数字，便于以后的计算
dictClassLabel = Counter(classLabelVector)
classLabel = []
kind = list(dictClassLabel)
for item in classLabelVector:
if item == kind[0]:
item = 1
elif item == kind[1]:
item = 2
else:
item = 3
classLabel.append(item)
return returnMat,classLabel#####将文本中的数据导入到列表
##绘图（可以直观的表示出各特征对分类结果的影响程度）
datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet.txt')
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,0],datingDataMat[:,1],15.0*array(datingLabels),15.0*array(datingLabels))
plt.show()
## 归一化数据,保证特征等权重
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))##建立与dataSet结构一样的矩阵
m = dataSet.shape[0]
for i in range(1,m):
normDataSet[i,:] = (dataSet[i,:] - minVals) / ranges
return normDataSet,ranges,minVals
##KNN算法
def classify(input,dataSet,label,k):
dataSize = dataSet.shape[0]
####计算欧式距离
diff = tile(input,(dataSize,1)) - dataSet
sqdiff = diff ** 2
squareDist = sum(sqdiff,axis = 1)###行向量分别相加，从而得到新的一个行向量
dist = squareDist ** 0.5
##对距离进行排序
sortedDistIndex = argsort(dist)##argsort()根据元素的值从大到小对元素进行排序，返回下标
classCount={}
for i in range(k):
voteLabel = label[sortedDistIndex[i]]
###对选取的K个样本所属的类别个数进行统计
classCount[voteLabel] = classCount.get(voteLabel,0) + 1
###选取出现的类别次数最多的类别
maxCount = 0
for key,value in classCount.items():
if value > maxCount:
maxCount = value
classes = key
return classes
##测试(选取10%测试）
def datingTest():
rate = 0.10
datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet.txt')
normMat,ranges,minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
testNum = int(m * rate)
errorCount = 0.0
for i in range(1,testNum):
classifyResult = classify(normMat[i,:],normMat[testNum:m,:],datingLabels[testNum:m],3)
print("分类后的结果为:,", classifyResult)
print("原结果为：",datingLabels[i])
if(classifyResult != datingLabels[i]):
errorCount += 1.0
print("误分率为:",(errorCount/float(testNum)))
###预测函数
def classifyPerson():
resultList = ['一点也不喜欢','有一丢丢喜欢','灰常喜欢']
percentTats = float(input("玩视频所占的时间比?"))
miles = float(input("每年获得的飞行常客里程数?"))
iceCream = float(input("每周所消费的冰淇淋公升数?"))
datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet2.txt')
normMat,ranges,minVals = autoNorm(datingDataMat)
inArr = array([miles,percentTats,iceCream])
classifierResult = classify((inArr-minVals)/ranges,normMat,datingLabels,3)
print("你对这个人的喜欢程度:",resultList[classifierResult - 1])Создайте новый файл test.py, чтобы понять результаты работы программы, код:
#coding:utf-8
from numpy import *
import operator
from collections import Counter
import matplotlib
import matplotlib.pyplot as plt
import sys
sys.path.append("D:\python\Mechine learing in Action\KNN")
import date
date.classifyPerson()Результат работы следующий:
Выше приведена сортировка и сводка этого алгоритма.