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