一、算法的提出与目的

1、算法的提出

我们知道电影可以按照题材分类，比如分为爱情片和动作片。暂且不讨论种类是怎么分的。
假设，这时有一个新的电影，怎么根据已有的数据（部分已经定义为爱情片和动作片的电影）来判断新的电影是什么种类的？

2、算法的工作原理

假设每个电影都有一定的特征值（比如接吻镜头，打斗镜头），合理的办法是，计算新的这个电影的特征值和所有电影的特征值之间的差，从差值最小的前k个电影题材的比例，来判断新的电影是什么题材的。

这也是k-近邻算法（KNN）的工作原理：输入没有标签的新数据后，将新数据的每个特征与训练样本中对应的特征进行比较，然后提取出训练样本中特征最相似的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就算算法名称的由来。
最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

3、算法的目的

可以应用k-近邻算法，根据样本数据，判断输入数据分别属于哪个分类。

二、算法的推导

k-近邻算法比较简单明了，就是计算已知类别数据集中的点与当前点之间的距离，用欧式距离公式来得到结果，没有什么推导的地方。

三、算法的代码实现

树立分块写代码的思想：
1、算法是一个函数，参数是特定的数据格式；
2、数据处理再单独写，把原数据处理成算法函数需要的形式。

1、算法的伪码（自己先想想伪码应该怎么写）

• 1 计算当前点与已知类别的数据集中每个样本点之间的距离
• 2 将已经计算出的距离，按照从小到大的顺序排列
• 3 选中前k个最小的距离，并计算出前k个中每个点对应的类别的比例
• 4 返回前k个点中类别比例最高的那一类作为当前点的预测分类

2、算法的代码

这是一个分类器，将其写成一个函数
所需要的数据：
一个矩阵（dataSet）~表示每个数据的每个特征值，
一个向量（labels）~每个数据对应的标签

代码经验

1、这里排列的思想比较有意思
先说argsort方法，返回“数组的值从小到大”的索引值。
原本数据是按照dataSet中的顺序排列的（并没有什么大小的意思），只不过，dataSet中的第m个数据，对应的是labels中的第m个标签。这是前面处理数据的结果。
矩阵整体的加减乘除运算并不改变数据位置，所以distances表示的还是原来的顺序的距离。
这时用argsort方法来返回的是“数组的值从小到大”的索引值。也就是说，distances按照结果中（sortedDis）前k个值进行索引的话，是原数组中（即distances中）最小的k个值。
比如，sortedDis中第一个值是156，那么说明distances[156]是distances列表中最小的值。同样，labels[156]就是最小的值对应的标签。
于是，用labels向量对sortedDis中前k个值（对应了distances中最小的前k个值的索引）进行索引，就能得到距离最小的前k个值的标签。
一步到位了。毕竟最后的目的是最小值的标签。

2、sorted函数的应用
sorted(iterable,key,reverse)三个参数
其中iterable表示可以迭代的对象，例如可以是dict.items()、dict.keys()等，key是一个函数，用来选取参与比较的元素。
这里的key函数是用operator模块中的itemgetter方法。
一般用的是lambda表达式，来表示取第几个元素用来比较。比如 key = lambda item:item[1]则表示取第一个元素。这是比较常用的sorted功能，见下面链接。
python的sorted函数对字典按key排序和按value排序

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]#采用这种方法来获得矩阵行数，也就是数据大小
#1、距离计算
    #整体的计算距离，其中tile函数比较好，直接把当前点扩展成了相同结构的矩阵
    #矩阵相减，矩阵平方，矩阵内部各行求和，矩阵元素开方，得到与每个数据之间的距离
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5

#2、将距离按照从小到大顺序排列，并且取出前k个最小的值的标签，都放到统计类数量的classcount中去  
    sortedDistIndicies = distances.argsort()     
    classCount={}          
    for i in range(k):#for循环和sortedDis的配合
        voteIlabel = labels[sortedDistIndicies[i]]
        #这里默认为0是比较好的，要是没有该标签，key的值为零以后加1，有标签，直接加1
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1

#3+4返回前k个点中类别比例最高的那一类作为当前点的预测分类
    #注意sorted函数的运用
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    #已经按照sorted排序好了， 种类出现最多的排在首位，所以可以按照【0】【0】索引了。
    return sortedClassCount[0][0]

四 实战

1 准备数据（准备数据是很重要很重要的事情）

我们需要把给定的训练数据，解析处理成算法需要的参数。简单点说，就是，给定的样本数据是不能直接用的，我们需要预处理一下，把这些文本数据处理成可以直接在函数里应用的参数的格式。

1.1单个文本文件_解析文本

这里应用《机器学习实战》这本书上的例子。
定义函数把数据预先处理成算法函数想要的结构，是第一步
定义一个函数，使得该函数的输入为文件名字符串，输出为训练样本矩阵和类标签向量。

将文本转化为算法需要参数的数据结构函数思路：

• 1既然想得到一个矩阵还有一个类标签向量，就要先知道矩阵的shape，列数可以事先查看一下就可以得到
• 2然而行数不好得到，可以用len(F.readlines)容易得到。
• 3得到shape之后赋初值全为零。
• 4解析得到的每行数据，有两个方面的数据，一个是输入的特征值，前面三个元素，最后一个是标签
• 5所以，可以用for循环加上切片的方式，把特征值赋给矩阵每一行。再把每行的最后一个值添加进标签向量之中。
• 6至此，得到一个矩阵还有一个向量。

def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())  #得到行数
    returnMat = zeros((numberOfLines,3)) #矩阵赋值       
    classLabelVector = []                        
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]#给矩阵每行赋特征值
        classLabelVector.append(int(listFromLine[-1]))#得到每行标签
        index += 1
    return returnMat,classLabelVector

1.2归一化数据

在应用KNN算法的时候，其中计算距离的法用的是欧氏距离公式，但是有一个缺点在于，如果特征的属性并不相同，可能造成权重一边倒的情况。比如这里用的例子，第一个特征是一年玩游戏的时间，第二个飞行常客里程数，那么与几十个冰淇淋相比，一定是成百上千的飞行里程数在公式中占据主导地位。这是不应该的。所以此时需要对每个特征进行归一化。

此处我们用的归一化，就是将取值范围的特征值转化到0-1之间。
newValue = (oldValue - min) / (max - min)

归一化特征值函数思路：
整体处理数据的思想，数据要按照整体进行处理

• 1 每个特征的最大，最小值可以通过mat.max(0)和mat.min(0)来求得。
• 2 构造一个新的归一化的矩阵，和原矩阵同shape。
• 3 直接把矩阵应用到公式中即可，其中减去最小值的那一项，可以用上面提到的tile函数来实现。

def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m,1))
    normDataSet = normDataSet/tile(ranges, (m,1))   #element wise divide
    return normDataSet, ranges, minVals

2 测试算法

算法的代码已经完成，需要输入的数据参数也已经处理好，接下来就是根据训练数据测试算法即可。

3 使用算法 （构建一个完整的系统）

算法不是测试完了就OK了，最重要的是实现算法的功能：根据输入的特征值，判断此人是否是海伦喜欢的类型。

• 1 应用input函数来使使用者能够输入数据特征
• 2 别忘了用float把input返回的字符串变成数字
• 3 对于输入的特征，千万别忘了也需要进行数据处理，此处需要归一化
• 4 输出结果：like or dislike

五 KNN的优缺点

优点：简单有效
缺点：

• 1必须保存全部数据集，可能会使用大量的存储空间。
• 2必须对每个数据计算距离，耗时。
• 3无法给出任何数据的基础结构信息，无法知道平均实例样本和典型实例样本具有什么特征。

PS1：

对于多文件（同一个文件夹下的多个文本文件）的数据处理方法。

• 1 用listdir函数获得该文件夹下的所有文件名并返回一个列表
• 2 用返回的列表，索引的方式获得每一个文件名（若需要的话，对每个文件名进行字符串处理得到想要的数据，比如类标签）
• 3 测试算法（同样，在运用算法函数之前，需要处理好数据，可以直接赋值给参数。）