小节内容

• 什么是KNN算法模型
• KNN工作原理
• KNN算法思想
• KNN算法流程

什么是KNN算法模型

• K-近邻（kNN，K-NearestNeighbor）算法是一种基本分类与回归方法，我们这里只讨论分类问题中的k-近邻算法。

其目标：K-近邻算法的输入为实例的特征向量（吃冰淇淋/喝水/活动时间），对应于特征工控的点，输出为实例的类别（非常热/一般热），可以取多累（非常热/一般热/舒适/一般冷/非常冷）。

• K-近邻算法假设给定一个训练数据集（随机访客），其中的实例类别已定（访客感受）。分类时，对新的实例（新游客），根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。

k近邻算法术属于有监督学习范畴。k近邻算法实际上利用数据集对特征向量空间进行划分，并作为其分类的“模型”。k值的选择、距离度量以及分类决策规则是k近邻算法的三个基本要素。

KNN工作原理

• 假设一个带有标签的样本数据集（训练样本集），包含每条数据与所属分类的对应关系。
• 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
• 计算新数据与样本数据集中每条数据的距离
• 对求得的所有距离进行排序（从小到大，越小表示越相似）
• 取前k（k<20的奇数）个样本数据对应的分类标签
• 求k个数据中出现次数最多的分类标签作为新数据的分类

KNN算法思想

• 计算已知类别中数据集的点与当前点的距离。[即计算所有样本点跟待分类样本之间的距离]
• 按照距离递增排序。[计算完样本距离后进行排序]
• 选取与当前距离最小的k个点。[选取距离样本最近的k个点]
• 确定前k个点所在类别的出现频率。[针对这k个点，统计下各个类别分别有多少个]
• 返回前k个点吹安频率最高的类别作为预测结果。[k个点中某个类别最多，就将样本划归该点]

KNN算法流程

• 搜集数据：数据采集过程，其分为结构化数据，半结构化数据和数据化数据。比如：网络爬取，数据可，文件等。
• 准备数据：格式化处理，对不同类别的数据进行统一的格式化处理。诸如：将pdf，word，excel，sql等等统一转化为txt文本。
• 分析数据：主要看看数据特点，有没有缺失值，数据连续性还是离散型，进而选择不同模型。诸如：可视化数据分析。
• 训练模型：不适用于KNN，但是在其它一些监督学习中会经常遇到，比如：朴素贝叶斯分类等。
• 应用算法：针对完善的模型进行封装重构，然后进行实际应用。

欧式距离代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def ComputeEuclideanDistance(x1,y1,x2,y2):
    """欧式距离计算：d=(x1-x2)^2+(y1-y2)^2"""
    d = math.sqrt(math.pow(x1-x2,2)+math.pow(y1-y2,2))
    return d

def EuclideanDistance(instance1,instance2,length):
    """欧式距离计算拓展"""
    d = 0
    for x in range(length):
        d += pow((instance1[x] - instance2[x]),2)
    return math.sqrt(d)
if __name__ == "__main__":
    d = ComputeEuclideanDistance(2,4,8,2)
    print(d)
    d = EuclideanDistance([2,4],[8,2],2)
    print(d)

6.324555320336759

6.324555320336759