冒泡~又是新的一周辣！：)今天又学习了之前简要扫过的K近邻算法（KNN）。

K近邻算法（KNN）

原理：

首先这是是一种常用于分类的算法，该方法的基本思路是：如果一个待分类样本在特征空间中的k个最相似(即特征空间中K近邻)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
其实也可以通俗地理解为古话常说的近朱者赤，近墨者黑。

下面通过例子的直观图解释：

image1.png

算法要素：

通过上图解释可以得到KNN算法的几个重要要素：
a.数据集：存在一个样本数据集，也称作训练集，样本数据集中每个样本是有标签的，即我们知道样本数据集中每一个样本的分类。当获取到一个没有标签的待分类样本时，将待分类样本与样本数据集中的每一个样本进行比较，找到与当前样本最为相近的K个样本，并获取这K歌样本的标签，最后，选择这k个样本标签中中出现次数最多的分类，作为待分类样本的分类。

image.png

d.K值的选取：K是一个自定义的常量。K值的选取会影响待分类样本的分类结果，会影响算法的偏差与方差。

接下来举个简单的例子，来解释算法的过程。

image.png

image.png

算法过程

a.计算已知类别数据集中的点与当前点之间的距离；
b.按照距离递增次序排序；
c.选取与当前点距离最小的k个点；
d.确定前k个点所在类别的出现频率；
e.返回前k个点所出现频率最高的类别作为当前点的预测分类。
比如，接上图的那个电影的例子，现在我这个k值取3，那么在电影例子中，按距离依次排序的三个点分别是动作片(108,5)、动作片(115,8)、爱情片(5,89)。在这三个点中，动作片出现的频率为三分之二，爱情片出现的频率为三分之一，所以该红色圆点标记的电影为动作片。

Python实现

（实现刚刚上面提到的电影的例子）

import numpy as np
import operator

"""
函数说明:创建数据集
Parameters: 无
Returns:
    group - 数据集
    labels - 分类标签
"""
def createDataSet():
    #四组二维特征
    group = np.array([[1,101],[5,89],[108,5],[115,8]])
    #四组特征的标签
    labels = ['爱情片','爱情片','动作片','动作片']
    return group, labels
"""
函数说明:kNN算法,分类器
Parameters:
    inX - 用于分类的数据(测试集)
    dataSet - 用于训练的数据(训练集)
    labes - 分类标签
    k - kNN算法参数,选择距离最小的k个点
Returns:
    sortedClassCount[0][0] - 分类结果
"""
def classify(inX, dataSet, labels, k):
    #numpy函数shape[0]返回dataSet的行数
    dataSetSize = dataSet.shape[0]
    #在列向量方向上重复inX共1次(横向)，行向量方向上重复inX共dataSetSize次(纵向)
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    #二维特征相减后平方
    sqDiffMat = diffMat**2
    #sum()所有元素相加，sum(0)列相加，sum(1)行相加
    sqDistances = sqDiffMat.sum(axis=1)
    #开方，计算出距离
    distances = sqDistances**0.5
    #返回distances中元素从小到大排序后的索引值
    sortedDistIndices = distances.argsort()
    #定一个记录类别次数的字典
    classCount = {}
    for i in range(k):
        #取出前k个元素的类别
        voteIlabel = labels[sortedDistIndices[i]]
        #dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
        #计算类别次数
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    #python3中用items()替换python2中的iteritems()
    #key=operator.itemgetter(1)根据字典的值进行排序
    #key=operator.itemgetter(0)根据字典的键进行排序
    #reverse降序排序字典
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    #返回次数最多的类别,即所要分类的类别
    return sortedClassCount[0][0]

if __name__ == '__main__':
    #创建数据集
    group, labels = createDataSet()
    print(group)
    #测试集
    a = [101,20] 
    b = [1,90]
    #kNN分类
    c = classify(a, group, labels, 3)
    d = classify(b, group, labels, 4)
    #打印分类结果
    print(c)
    print(d)·

结果：

image.png

Matlab实现

trainData = [1,101;5,89;108,5;115,8];
trainClass = [1,1,2,2];
testData = [101,20];
testData = [1,90];
k = 3;
%% distance
row = size(trainData,1);
col = size(trainData,2);
test = repmat(testData,row,1);
dis = zeros(1,row);
for i = 1:row
    diff = 0;
    for j = 1:col
        diff = diff + (test(i,j) - trainData(i,j)).^2;
    end
    dis(1,i) = diff.^0.5;
end
%% sort
jointDis = [dis;trainClass];
sortDis= sortrows(jointDis');
sortDisClass = sortDis';
%% find
class = sort(2:1:k);
member = unique(class);
num = size(member);

max = 0;
for i = 1:num
    count = find(class == member(i));
    if count > max
        max = count;
        label = member(i);
    end
end
disp('分类结果为：');
fprintf('%d\n',label)

结果：

image.png

参考资料：(http://cuijiahua.com/blog/2017/11/ml_1_knn.html)
(https://blog.csdn.net/wangmumu321/article/details/78576916)

Ending~你今天学习了吗？