1, 概述: 也称为 K 最近邻算法, 原理为搜索最近的 k 个已知类别样本, 用于未知类别样本的预测.
对于分布不均匀的几个样本结果可能会受 k 取值的影响, 通常情况下 k 值一般取奇数
2, 衡量相似性指标方式: 欧式距离, 曼哈顿距离, cos 余弦值, 杰卡德相似系数等等
3, 过程:
确定 k
确定样本间相似度的度量指标, 形成簇
根据各簇下类别最多的分类作为样本预测点
4, 避免 k 值设定出现过拟合 (K 值过小) 和欠拟合 (K 值选择过大) 现象
对于 K 值设定过大的情况, 可以更改设定权重为距离的倒数. 另外一种常用的方式为多重交叉验证, k 取不同的值, 在每个 k 值下执行 m 重交叉验证, 最后选定平均误差最小的 k 值.
5, 余弦相似度
杰卡德相似系数 (常用于用户推荐算法) 值越大相似性越大
以上距离法构建样本时, 一是需注意变量的数值化, 若某个变量为离散型字符串, 需要数值化处理(0,1,2...). 二是防止受数值变量的量纲影响, 量纲可能影响距离, 必要时需要进行转化, 缩小归一化处理.
6, 模型运行搜索方法
模型建立好以后常见的几种搜寻方法
- import CSV
- import random
- import math
- import operator
- def loadDataset(filename, split, trainingSet = [], testSet = []):
- with open(filename, 'rt') as csvfile:
- lines = CSV.reader(csvfile)
- dataset = list(lines)
- print(len(dataset))
- for x in range(len(dataset)-1): #0-149
- for y in range(4): #0-3
- 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)
- def getNeighbors(trainingSet, testInstance, k):
- distances = []
- length = len(testInstance)-1
- for x in range(len(trainingSet)):
- #testinstance
- dist = euclideanDistance(testInstance, trainingSet[x], length)
- distances.append((trainingSet[x], dist))
- #distances.append(dist)
- distances.sort(key=operator.itemgetter(1)) # 取元祖第一个域进行排序
- neighbors = []
- for x in range(k): #取 distances 数组前三项距离最小元祖里面的数组
- 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.0
- def main():
- #prepare data
- trainingSet = []
- testSet = []
- split = 0.67
- loadDataset(r'irisdata.txt', split, trainingSet, testSet)
- print ('Train set:' + repr(len(trainingSet)))
- print ('Test set:' + repr(len(testSet)))
- #generate predictions
- predictions = []
- k = 3
- for x in range(len(testSet)): # 0 - 测试集长度
- # trainingsettrainingSet[x]
- 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()
来源: http://www.bubuko.com/infodetail-3259155.html