k-近邻算法（KNN）
输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应特征进行比较，然后提取样本集中特征最相似的分类标签。一般来说，选择样本集中前k个最相似的数据，这k个数据中出现次数最多的分类就是新数据的预测分类。
示例说明
预测电影类型，样本集是一系列的已知分类的电影，有两类：
- 爱情
- 动作
这里选择的特征是： - 接吻次数
- 打斗次数
一个样本可以表示为（20，3，a）：20次接吻镜头，3次打斗镜头的爱情电影。
然后求（25，10，？）
用欧式距离表示相似程度，距离越近表明越相似： d=((20-25)**2 + (3-10)**2)**0.5
k-近邻算法函数
import numpy as np
def classify_self(inX, dataSet, labels, k):
'''
自己抄一遍KNN的算法函数
inX: 输入待预测的特征向量
dataSet: 训练样本的特征值
labels: 训练样本的目标值
k: kNN的参数
'''
dataSetSize = dataSet.shape[0]
diffMat = dataSet - np.tile(inX, (dataSetSize, 1))
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances**0.5
sortedDistIndicies = distances.argsort()
classCount = {}
for i in range(k):
voteIlable = labels[sortedDistIndicies[i]]
classCount[voteIlable] = classCount.get(voteIlable, 0) + 1
sortedClassCount = sorted(classCount.items(), key= lambda x: x[1], reverse=True)
return sortedClassCount[0][0]
数值归一化
有些特征的数值本身差异就大，不对数据处理就套用kNN就会放大这个差异大的特征的权重。
- 考察约会对象魅力程度的特征：
- 每年飞行里程
- 每周吃冰淇淋数量
- 玩游戏时间占用百分比
飞行里程本身一个样本400公里，另一个2000公里，两个样本实际也就差个国际长途飞行的距离而已。1600的平方立马就完全可以忽略几个冰淇淋和游戏百分比的数值差异了。
而实际情况是，这几个特征等权重（同样重要指标）。
So，数值归一化：
new_value = (origin_value - min)/(max - min)- min和max表示特征的最小值和最大值
- 0 <= new_value <= 1
数值归一化后所有特征就等权重了，因为数值区间一致了。
import numpy as np
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = np.zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - np.tile(minVals, (m,1))
normDataSet = normDataSet/tile(ranges, (m,1)) #element wise divide
return normDataSet, ranges, minVals
