KNN算法简单应用
这里是写给小白看的，大牛路过勿喷。
1 KNN算法简介
KNN（K-Nearest Neighbor）工作原理：存在一个样本数据集合，也称为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类对应的关系。输入没有标签的数据后，将新数据中的每个特征与样本集中数据对应的特征进行比较，提取出样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k近邻算法中k的出处，通常k是不大于20的整数。最后选择k个最相似数据中出现次数最多的分类作为新数据的分类
2 KNN算法优缺点
优点：精度高，对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
做一个简单的应用：
一种花叫做虹膜花：
- from sklearn import neighbors
- from sklearn import datasets
- knn = neighbors.KNeighborsClassifier()
- iris = datasets.load_iris()
- knn.fit(iris.data, iris.target)
- # 当数据为0.1, 0.2, 0.3, 0.4时，预测它是什么花
- predictedLabel = knn.predict([[0.1, 0.2, 0.3, 0.4]])
- print(predictedLabel)
- 5.1,3.5,1.4,0.2,Iris-setosa
- 4.9,3.0,1.4,0.2,Iris-setosa
- 4.7,3.2,1.3,0.2,Iris-setosa
- 4.6,3.1,1.5,0.2,Iris-setosa
- 5.0,3.6,1.4,0.2,Iris-setosa
- 5.4,3.9,1.7,0.4,Iris-setosa
- 4.6,3.4,1.4,0.3,Iris-setosa
- 5.0,3.4,1.5,0.2,Iris-setosa
导入几个基本的库：
- import csv
- import random
- import math
- import operator
全局定义两个集合：训练集、测试集
- # 训练集
- trainingSet = []
- # 测试集
- testSet = []
读取数据并做一些初步的处理：
传入一个分割概率，随机划分训练集和测试集
- def loadDataset(filename, split):
- with open(filename, 'r') as csvfile:
- lines = csv.reader(csvfile)
- dataset = list(lines)
- 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])
- else:
- testSet.append(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个数据：
计算训练集中每一项和该实例的欧氏距离，取最小的k个距离
- def getNeighbors(k, testInstance):
- 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
获取的这些k项未必是同一类，接下来统计类别个数，并返回出现次数最多的类作为最终的结果：
- 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(predictions):
- correct = 0
- for x in range(len(testSet)):
- if testSet[x][-1] == predictions[x]:
- correct += 1
- return (correct / float(len(testSet))) * 100.0
主函数：
- if __name__ == '__main__':
- main()
- def main():
- split = 0.70
- loadDataset(r'D:\ml\irisdata.txt', split)
- print('Train set: ' + repr(len(trainingSet)))
- print('Test set: ' + repr(len(testSet)))
读取后打印下个数：
- Train set: 102
- Test set: 48
接下来预测：
- predictions = []
- k = 3
- for x in range(len(testSet)):
- neighbors = getNeighbors(k, testSet[x])
- result = getResponse(neighbors)
- predictions.append(result)
- print('>predicted=' + repr(result) + ', actual=' + repr(testSet[x][-1]))
看一下预测的一部分结果：
发现基本预测准确，测试精确度：
- accuracy = getAccuracy(predictions)
- print('Accuracy: ' + repr(accuracy) + '%')
发现精确度很高：
由于处理数据时候采用随机划分的方式，可以反复运行测试，发现准确率基本在90%到96%，说明这个模型是合适的
小结：
KNN是简单有效的分类数据算法，在使用时必须有训练样本数据，还要计算距离，如果数据量非常大会非常消耗空间和时间。它的另一个缺陷是无法给出任何数据的基础结构信息，因此我们无法平均实例样本和典型实例样本具体特征，