【Machine Learning】KNN算法虹膜图片识别

最近邻居法采用向量空间模型来分类，概念为相同类别的案例，彼此的相似度高，而可以借由计算与已知类别案例之相似度，来评估未知类别案例可能的分类。K-NN是一种基于实例的学习，或者是局部近似和将所有计算推迟到分类之后的惰性学习。k-近邻算法是所有的机器学习算法中最简单的之一。无论是分类还是回归，衡量邻居的权重都非常有用，使较近邻居的权重比较远邻居的权重大。例如，一种常见的加权方案是给每个邻居权重赋值为1/ d，其中d是到邻居的距离。邻居都取自一组已经正确分类（在回归的情况下，指属性值正确）的对象。虽然没要求明确的训练步骤，但这也可以当作是此算法的一个训练样本集。k-近邻算法的缺点是对数据的局部结构非常敏感。本算法与K-平均算法（另一流行的机器学习技术）没有任何关系，请勿与之混淆。

1.2 举例分析一

我们提取电影的主要特征信息，特征选择：电影名称、打斗次数、接吻次数、电影类型。主要借助打斗和接吻特征判断电影属于那种类型（爱情片/动作片）.将采用KNN的方法进行模型训练，因为KNN属于有监督学习，因此设定一定规模的训练集进行模型训练，然后对测试数据进行分类预测，具体如图1所示：

图2  电影信息特征转化

下面判断未知电影G点属于Romance或Action那种类型？不妨以图3形式化描述更好理解，假设黑色的豆子是动作片，绿色豆子是历史片，红色的豆子是爱情片。一部新电影G点到底属于哪个类型。主要判定G点周围的点属于哪个类型，至于G点周围如何设定，这就是K值的设置。K值不同直接影响分类结果，这个后续详细介绍。K的设定一般都是1,3,5,7,9等这样的奇数。其理由是因为采用少数服从多数的原理，不然设为偶数出现中立的情况就没有办法分类了。下图中绿色的原点周围大多属于绿豆，所以规为绿色豆子即【爱情片】。具体算法和代码后文介绍。 

1.3 举例分析二

绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。如图4所示：

• 简单、易于理解、容易实现
• 无需估计参数
• 无需训练
• 通过对K的选择可具备丢噪音数据的健壮性
• 适合对稀有事件进行分类
• 特别适合于多分类问题(multi-modal,对象具有多个类别标签)，kNN比SVM的表现要好

• 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。
• 需要大量空间储存所有已知实例
• 可理解性差，无法给出像决策树那样的规则
• 算法复杂度高（需要比较所有已知实例与要分类的实例）

'加载数据集,split划分数据集为训练集和测试集'
def loadDataset(filename,split,trainingSet=[],testSet=[]):
with open(filename,'r') as csvfile:
lines = csv.reader(csvfile)
dataset = list(lines)
# print(dataset[:20])
for x in range(len(dataset)-1):
for y in range(4):
dataset[x][y] = float(dataset[x][y])
if random.random() < split:
trainingSet.append(dataset[x])
# print(dataset[x])
else:
testSet.append(dataset[x])
# print('-->',dataset[x])

'返回最近的K个label'
def getNeighbors(trainingSet,testInstance,k):
distances = []
length = len(testInstance)-1
for x in range(len(trainingSet)):
dist = euclideanDistance(testInstance, trainingSet[x], length)
distances.append((trainingSet[x], dist))
distances.sort(key=operator.itemgetter(1))
neighbors = []
for x in range(k):
neighbors.append(distances[x][0])
return neighbors

'计算距离'
def euclideanDistance(instance1,instance2,length):
distance = 0
for x in range(length):
distance += pow((instance1[x]-instance2[x]),2)
return math.sqrt(distance)

import math
def ComputeEuclideanDistance(x1, y1, x2, y2):
d = math.sqrt(math.pow((x1-x2), 2) + math.pow((y1-y2), 2))
return dd_ag = ComputeEuclideanDistance(3, 104, 18, 90)print d_ag

'根据投票进行分类划分'
def getResponse(neighbors):
classVotes = {}
for x in range(len(neighbors)):
response = neighbors[x][-1]
if response in classVotes:
classVotes[response] += 1
else:
classVotes[response] = 1
sortedVotes = sorted(classVotes.items(),key=operator.itemgetter(1),reverse=True)
return sortedVotes[0][0]

'预测结果，算出精确度'
def getAccuracy(testSet, predictions):
correct = 0
for x in range(len(testSet)):
if testSet[x][-1] == predictions[x]:
correct += 1
return (correct/float(len(testSet)))*100.0

import csv
import math
import random
import operator'''
Description:python调用机器学习库scikit-learn的K临近算法，实现花瓣分类
Author:Bai Ningchao
DateTime:2017年1月3日15:07:25
Blog URL:http://www.cnblogs.com/baiboy/
Document：http://scikit-learn.org/stable/modules/neighbors.html
''''加载数据集,split划分数据集为训练集和测试集'
def loadDataset(filename,split,trainingSet=[],testSet=[]):
with open(filename,'r') as csvfile:
lines = csv.reader(csvfile)
dataset = list(lines)
# print(dataset[:20])
for x in range(len(dataset)-1):
for y in range(4):
dataset[x][y] = float(dataset[x][y])
if random.random() < split:
trainingSet.append(dataset[x])
# print(dataset[x])
else:
testSet.append(dataset[x])
# print('-->',dataset[x])'计算距离'
def euclideanDistance(instance1,instance2,length):
distance = 0
for x in range(length):
distance += pow((instance1[x]-instance2[x]),2)
return math.sqrt(distance)'返回最近的K个label'
def getNeighbors(trainingSet,testInstance,k):
distances = []
length = len(testInstance)-1
for x in range(len(trainingSet)):
dist = euclideanDistance(testInstance, trainingSet[x], length)
distances.append((trainingSet[x], dist))
distances.sort(key=operator.itemgetter(1))
neighbors = []
for x in range(k):
neighbors.append(distances[x][0])
return neighbors'根据投票进行分类划分'
def getResponse(neighbors):
classVotes = {}
for x in range(len(neighbors)):
response = neighbors[x][-1]
if response in classVotes:
classVotes[response] += 1
else:
classVotes[response] = 1
sortedVotes = sorted(classVotes.items(),key=operator.itemgetter(1),reverse=True)
return sortedVotes[0][0]'预测结果，算出精确度'
def getAccuracy(testSet, predictions):
correct = 0
for x in range(len(testSet)):
if testSet[x][-1] == predictions[x]:
correct += 1
return (correct/float(len(testSet)))*100.0def main():
trainingSet = []
testSet = []
split = 0.7 # 2/3训练集，1/3测试集
loadDataset(r'../datafile/irisdata.txt',split,trainingSet,testSet)
print('Train set: ' + repr(len(trainingSet)))
print('Test set: ' + repr(len(testSet)))
#generate predictions
predictions = []
k =5
for x in range(len(testSet)):
neighbors = getNeighbors(trainingSet, testSet[x], k)
result = getResponse(neighbors)
predictions.append(result)
print ('>predicted=' + repr(result) + ', actual=' + repr(testSet[x][-1]))
print ('predictions: ' + repr(predictions))
accuracy = getAccuracy(testSet,predictions)
print('Accuracy: ' + repr(accuracy) + '%')if __name__ == '__main__':
main()