1、综述
1.1 Cover和Hart在1968年提出了最初的邻近算法
1.2 分类(classification)算法
1.3 输入基于实例的学习(instance-based learning), 懒惰学习(lazy learning)
2、例子
预测电影的类型
3、算法详述
3.1算法流程：
为了判断未知实例的类别，以所有已知类别的实例作为参照，选择K，计算未知实例与已知实例的距离。
选择最近K个已知实例，根据少数服从多数的投票法则（majority-voting），让未知实例归类为K个最邻近样本中最多数的类别。
3.2细节，关于距离的衡量公式
3.2.1Euclidean Distance 定义
其他距离衡量：余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance ）
3.3举例
4、算法的优缺点
简单、易于理解、容易实现、通过对K的选择可具备丢噪音数据的健壮性
算法的缺点：
需要大量空间储存所有已知实例 ，算法复杂度高（需要比较所有已知实例与要分类的实例），当其样本分布不平衡时，比如其中一类样本过大（实例数量过多）占主导的时候，新的未知实例容易被归类为这个主导样本，因为这类样本实例的数量过大，但这个新的未知实例实际并木接近目标样本。
5、算法改进：考虑距离，然后加上算法的权重
算法实现（Python）
from sklearnimport neighbors
#临近算法包含在这个类中
from sklearnimport datasets
#导入数据集
knn=neighbors.KNeighborsClassifier()
#调用knn的分类器
iris=datasets.load_iris()#返回一个数据集复制到iris上面
print(iris)
knn.fit(iris.data, iris.target)
#建立模型，传入特征值和目标值
predictedLabel=knn.predict([[0.1,0.2,0.3,0.4]])
print (predictedLabel)
import csv
import random
import operator
import math
#装入数据集
def loadDataset(filename,split,trainset=[],testset=[]):
with open(filename,'rt')as csvfile:
lines=csv.reader(csvfile)
dataset=list(lines)
for xin range(len(dataset)-1):
for yin range(4):
dataset[x][y]=float(dataset[x][y])
if random.random()
trainset.append(dataset[x])
else:
testset.append(dataset[x])
def enclideanDistance(instance1,instance2,length):
distance=0
for xin range(length):
distance+=pow((instance1[x]-instance2[x]),2)
return math.sqrt(distance)
#测试距离
def getNeighbors(trainset,testInstance,k):
distance=[]
length=len(testInstance)-1
for xin range(len(trainset)):
dist=enclideanDistance(testInstance, trainset[x], length)
distance.append((trainset[x],dist))
distance.sort(key=operator.itemgetter(1))
neighbors=[]
for xin range(k):
neighbors.append(distance[x][0])
return neighbors
#统计
def getResponse(neighbors):
classVotes={}
for xin range(len(neighbors)):
response=neighbors[x][-1]
if responsein 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,prediction):
correct=0
for xin range(len(testSet)):
if testSet[x][-1]==prediction[x]:
correct+=1
return (correct/float(len(testSet)))*100
def main():
trainSet=[]
testSet=[]
split=0.67
loadDataset(r'iris.data.txt', split, trainSet, testSet)
print ('Train set:'+repr(len(trainSet)))
print ('Test set:'+repr(len(testSet)))
prediction=[]
k=3
for xin range(len(testSet)):
neighbors=getNeighbors(trainSet, testSet[x], k)
result=getResponse(neighbors)
prediction.append(result)
accuracy=getAccuracy(testSet, prediction)
print('Accuracy:'+repr(accuracy))
main()
网友评论