手动实现KNN算法

KNN算法又称最邻近算法，算法思想：如果一个样本在特征空间中的k个相似中大多数属于某一类，该样本也属于这一类别。KNN算法是用距离衡量样本之间的相似度。

本文使用python手动实现KNN算法：

#读取文件，并将特征和类别分别存入二维矩阵和list中

def file2matrimx(filename):

fr =open(filename)

arrayOfLines = fr.readlines()

#获取行数

    numOfLen =len(arrayOfLines)

#创建一个numOfLen行，3列的矩阵,用于存放特征

    returnMat = np.zeros((numOfLen,3))

#存放label

    classLabelVector = []

index =0

    for linein arrayOfLines:

line = line.strip()

listFromLine = line.split("\t")

if len(listFromLine) !=1:

listFromLine =list(map(float,listFromLine))

returnMat[index,:] = listFromLine[0:3]

classLabelVector.append(listFromLine[-1])

index +=1

    #返回特征数组和标记

    return returnMat,classLabelVector

大部分的机器学习方法都需要将数据归一化，本文使用最大最小值归一化方法

def autoNurm(dataSet):

#返回每一列的最小值，dataSet.min(1)为返回每一行的最小值

    minVals = dataSet.min(0)

#同上

    maxVals = dataSet.max(0)

#使用最大最小值归一化

    ranges = maxVals - minVals

#统计行数

    m = dataSet.shape[0]

#数据集数据都减一个最小值，再除以最大值减去最小值的差

    normDataSet = dataSet - np.tile(minVals,(m,1))

normDataSet = normDataSet/np.tile(ranges,(m,1))

#返回归一化数据，ranges（最大值减最小值），最小值

return normDataSet,ranges,minVals

#KNN的具体实现，采用欧氏距离计算数据之间的距离

def classify(normData,dataSet,labels,k):

#统计行数

    dataSetSize = dataSet.shape[0]

#计算待测点到其他点的欧式距离

    diffMat = np.tile(normData,(dataSetSize,1))-dataSet

sqDiffMat = diffMat **2

    sqDistance = sqDiffMat.sum(axis=1)

distance = sqDistance **0.5

    #按照diatance的大小排序(由小到大)，并得出点在数据集中的下标

    sortDistance = distance.argsort()

#保存标记出现的次数

    classCount = {}

for iin range(k):

#获取类别

votelabel = labels[sortDistance[i]]

#给相同的类别加一

        classCount[votelabel] = classCount.get(votelabel,0)+1

        #按照v排序

        sortClassCount =sorted(classCount.items(),key=lambda x:x[1],reverse=True)

return sortClassCount[0][0]

def datingClassTest():

#定义测试集占总数据集的比例

    hoRatio =0.1

    #获取特征集和标记

    datingMat,datingLabel = file2matrimx("d:/datingTestSet2.txt")

#获取归一化数据

    normMat,ranges,minVals = autoNurm(datingMat)

for i  in range(numTestVecs):

#得到预测结果

    classifyResult = classify(normMat[i,:],normMat[numTestVecs:m,:],datingLabel[numTestVecs:m],4)

print("模型预测值：",classifyResult,",真实值：",datingLabel[i])

erroResult =0

    if(classifyResult != datingLabel[i]):

erroResult = erroResult +1

errorRate = erroResult/numTestVecs

print("numTestVecs:",numTestVecs)

trueRate =1-errorRate

print("错误率：",(str(errorRate)))

return 1-errorRate

#测试KNN算法的优劣：

def classifyPerson():

resultList = ['没感觉','看起来还行','极具魅力']

input_man = [30000,123,1]

datingDataMat,labels = file2matrimx('d:/datingTestSet2.txt')

normMat,ranges,minVals = autoNurm(datingDataMat)

result = classify((input_man-minVals)/ranges,normMat,labels,3)

print("这个人：",resultList[result-1])

if __name__ =='__main__':

acc = datingClassTest()

if(acc>0.9):

classifyPerson()