KNN (k-近邻算法)
其工作原理是： 存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都有存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中的对应特征值进行比较，然后算法提取样本集中特征最相似的数据的分类标签。一般的，选择样本数据集中前k个最相似的数据，通常k 是不大于20 的整数，最后选择k个最相似的数据中出现次数最多的分类，最为新数据的分类。
使用欧式距离公式来计算向量之间的距离公式:
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize,1)) - dataSet
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1) # 每一列向量相加
distances = sqDistances**0.5
sortedDistIndicies = distances.argsort() # 返回排列后的index
classCount = {}
# 依次取出最近的样本numpy数据
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) +1
#对类别出现的频次进行排序，从高到低
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1) , reverse=True)
print '[*] ', sortedClassCount
return sortedClassCount[0][0]
约会网站例子
根据约会网站收集的样本数据来改进配对效果
样本数据包含三种特征,
- 飞行历程数
- 玩游戏所耗的时间比
- 每周消费冰淇淋公升数
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
72993 10.141740 1.032955 1
35948 6.830792 1.213192 3
42666 13.276369 0.543880 3
67497 8.631577 0.749278 1
...
最后一列数据表示不喜欢，魅力一般，具有魅力
使用图表来分析这些特征，不同颜色区分不同的类别
以第二列和第三列数据分别作为x,y轴
以第一列和第二列分别作为x,y轴
从中可以当以第一列和第二列数据来画图表时，可以明显的类别效果
归一化处理
进行归一化处理的原因是样本数据特征值之间相差较大。
归一化处理公式:
newValue = (oldValue - min) / (max -min)
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals , (m,1))
normDataSet = normDataSet/ tile(ranges,(m,1))
return normDataSet, ranges, minVals
最后代码
使用分类器分类后，计算错误率，当错误率在一定范围时，这个分类器还是有效的。
#-*- coding: utf-8 -×—
from numpy import *
import operator
def file2matrix(filename):
fr = open(filename)
array0Line = fr.readlines()
numberOfLines = len(array0Line)
returnMat = zeros((numberOfLines,3))
classLabelVector = []
index = 0
for line in array0Line:
line = line.strip()
listFromLine = line.split('\t')
returnMat[index,:] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index +=1
return returnMat, classLabelVector
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals , (m,1))
normDataSet = normDataSet/ tile(ranges,(m,1))
return normDataSet, ranges, minVals
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = 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
#对类别出现的频次进行排序，从高到低
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1) , reverse=True)
print '[*] ', sortedClassCount
return sortedClassCount[0][0]
def datingClassTest():
# 设定测试数据的比例
hoRatio = 0.10
datingDataMat, datingLabels = file2matrix("datingTestSet2.txt")
normMat, ranges, minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
numTestVecs = int(m*hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,:], datingLabels[numTestVecs:m],3)
print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
if (classifierResult != datingLabels[i]): errorCount +=1
print "the total error rate is: %f" % (errorCount / float(numTestVecs))
datingClassTest()
测试结果
3.png
