python机器学习(一)KNN算法
一 算法理论
K最近邻(k-Nearest Neighbor,KNN)分类算法可以说是最简单的机器学习算法了。它属于监督学习的一种。它采用测量不同特征值之间的距离方法进行分类。它的思想很简单:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。
上图中要确定测试样本绿色属于蓝色还是红色。
显然,当K=3时,将以1:2的投票结果分类于红色;而K=5时,将以3:2的投票结果分类于蓝色。
K-近邻算法的具体思想如下:
(1)计算已知类别数据集中的点与当前点之间的距离
(2)按照距离递增次序排序
(3)选取与当前点距离最小的k个点
(4)确定前k个点所在类别的出现频率
(5)返回前k个点中出现频率最高的类别作为当前点的预测分类
这里所说的距离,一般最常用的就是多维空间的欧式距离。这里的维度指特征维度,即样本有几个特征就属于几维。
二 python实现
1计算欧式距离
import math
def computer_euclid_distance(x1,y1,x2,y2):d=math.sqrt(math.pow((x1-x2),2)+math.pow((y1-y2),2))
return d
##pow(x,y) 计算x的y次方 即,x^y
computer_euclid_distance(2,4,5,6) 结果是:3.605551275463989
2.鸢尾花数据拟合
from sklearn import neighbors
from sklearn import datasets
import numpy as np
knn=neighbors.KNeighborsClassifier()iris=datasets.load_iris()#导入鸢尾花数据库
print(iris)
knn.fit(iris.data,iris.target) # 利用函数拟合
predictde_lable=knn.predict(np.array([0.1,0.2,0.3,0.4]).reshape(1,-1)) ##输入点集预测
print(predictde_lable)
结果是[0]
3.knn聚类方法
import numpy as np
import matplotlib.pyplot as plt
import operator
group = np.array([[2, 5], [3, 6], [1, 7], [6, 8]]) ##创建数据集 第一二个点是一类,后两个点是一类
labels = [1,1,0,0]
return group, labels
def classify(target_plot, dataset, labels, k):
"""
target_plot 是输入的测试样本,是一个[x, y]样式的
dataset 是训练样本集
labels 是训练样本标签
是top k最相近的
"""
# shape返回矩阵的[行数,列数],
# 那么shape[0]获取数据集的行数,
# 行数就是样本的数量
dataSetSize = dataset.shape[0]
"""
下面的求距离过程就是按照欧氏距离的公式计算的。
即 根号(x^2+y^2)
"""
#
diffMat = np.tile(target_plot, (dataSetSize, 1)) - dataset
sqDiffMat = diffMat ** 2
sqDistance = sqDiffMat.sum(axis=1)
distance = sqDistance ** 0.5
sortedDistIndicies =distance.argsort()
# 存放最终的分类结果及相应的结果投票数
classCount = {}
for i in range(k):voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
if __name__== "__main__":
dataset, labels = createDataSet()
target_plot = [1, 1]
draw_picture(target_plot)
className = classify(target_plot, dataset, labels, 3)
print('the class of test sample is %s' %className)
从图中可以看出,蓝色圆点属于第二类,红色的点属于第一类,黑色 的点是目标点,属于第一类。
几点说明:
1.tile函数
tile属于numpy模块下边的函数 tile(A, reps)返回一个shape=reps的矩阵,矩阵的每个元素是A 比如 A=[0,1,2] 那么,tile(A, 2)= [0, 1, 2, 0, 1, 2] tile(A,(2,2)) = [[0, 1, 2, 0, 1, 2], [0, 1, 2, 0, 1, 2]]
tile(target,(4,1))
array([[1, 1],[1, 1],
[1, 1],
[1, 1]])
diffMat = np.tile(target_plot, (dataSetSize, 1)) - dataset
print(diffMat)
[[-1 -4]
[-2 -5]
[ 0 -6]
[-5 -7]]
sqDiffMat = diffMat ** 2
print(sqDiffMat)
sqDistance = sqDiffMat.sum(axis=1)
distance = sqDistance ** 0.5
axis=1表示按照横轴,sum表示累加,即按照行进行累加。
[[ 1 16][ 4 25]
[ 0 36]
[25 49]]
sortedDistIndicies =distance.argsort()
按照升序进行快速排序,返回的是原数组的下标。 比如,x = [30, 10, 20, 40] 升序排序后应该是[10,20,30,40],他们的原下标是[1,2,0,3] 那么,numpy.argsort(x) = [1, 2, 0, 3]# 投票过程,就是统计前k个最近的样本所属类别包含的样本个数
for i in range(k):
# index = sortedDistIndicies[i]是第i个最相近的样本下标
# voteIlabel = labels[index]是样本index对应的分类结果('1' or '2')
voteIlabel = labels[sortedDistIndicies[i]]
# classCount.get(voteIlabel, 0)返回voteIlabel的值,如果不存在,则返回0
# 然后将票数增1
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# 把分类结果进行排序,然后返回得票数最多的分类结果
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
参考:https://www.cnblogs.com/hemiy/p/6155425.html