K Nearest Neighbour Cluster Algorithm

$Machine learning = Representation + Optimization + Evaluation$
机器学习是建立/求解/评估模型的一个过程。

kNN算法

输入: 训练实例集 $T = {(x_{1},y_{1}),(x_{2},y_{2}),\cdots,(x_{N},y_{N}),}$
其中$x_{i}$为实例的特征向量，$y_{i}$为实例的类别

输出: 实例$x$所属的类$y$
(1) 根据给定的距离度量，在$T$中找到和$x$最近邻的$k$个点，记为邻域$N_{k}(x)$
(2) 在邻域$N_{k}(x)$中根据分类决策规则(如多数表决)决定$x$所属的类$y$
$$
y = \arg \mathop{\max}{c{j}} \mathop{\sum}{x{i} \in N_{k}(x)} I(y_{i}=c_{j})
$$
Here $i=1,2,\cdots,N; j=1,2,\cdots,k$

kNN模型三要素：k值，距离度量以及分类决策规则。

距离度量

设特征空间$\chi$是$n$维实数向量空间$R^{n}$,$x_{i},x_{j} \in \chi$,则有
$$
L_{p}(x_{i},x_{j})=\left( \sum_{l=1}^{n} \left| x_{i}^{l}- x_{j}^{l}\right|^{p} \right)^{\frac{1}{p}}
$$
此处$p \ge 1$，1对应Manhattan距离，2即为常用的欧式距离，

实际例子(电影分类)

欧式距离定义分类方式。(首先需要归一化数值)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun May  9 16:13:12 2020

@author: chen
"""
from matplotlib.font_manager import FontProperties
import matplotlib.lines as mlines
import matplotlib.pyplot as plt
import time
import numpy as np
import operator

"""
函数说明：创建数据集

Parameters:
    None
    
Returns:
    group - 数据集
    labels - 分类标签
"""

def createDataSet():
    # 二维特征
    group = np.array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]])
    # 对应的标签
    labels = ['爱情片','爱情片','爱情片','动作片','动作片','动作片']
    return group, labels

定义欧氏距离并生成字典获得排序判断

"""
函数说明：kNN算法，分类器

Parameters:
    inX - 用于分类的数据（测试集）
    dataSet - 用于训练的数据（训练集）（n*1维列向量）
    labels - 分类标准（n*1维列向量）
    k - kNN算法参数，选择距离最小的k个点
    
Returns:
    sortedClassCount[0][0] - 分类结果
"""
def classify0(inX, dataSet, labels, k):
    # numpy函数shape返回数组维度，shape[0]即行数
    dataSetSize = dataSet.shape[0]
    # 将inX重复dataSetSize次并排成一列
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    #计算欧式距离
    # 二维特征相减后平方（用diffMat的转置乘diffMat）
    sqDiffMat = diffMat**2
    # sum()所有元素相加，sum(0)列相加，sum(1)行相加
    sqDistances = sqDiffMat.sum(axis=1)
    # 开方，计算出距离
    distances = sqDistances**0.5
    # argsort函数返回的是distances值从小到大的--索引值
    sortedDistIndicies = distances.argsort()
    #与训练集本集作对比
    # 定义一个记录类别次数的字典
    classCount = {}
    # 选择距离最小的k个点
    for i in range(k):
        # 取出前k个元素的类别
        voteIlabel = labels[sortedDistIndicies[i]]
        # 字典的get()方法，返回指定键的值，如果值不在字典中返回0
        # 计算类别次数
        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]

def main():
    # 创建数据集
    group, labels = createDataSet()
    # 测试集
    test = [18,90]
    # kNN分类
    test_class = classify0(test, group, labels, 3)
    # 打印分类结果
    print(test_class)
    
main()