最近规则分类算法（KNN算法）

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()