KNN算法

“””

author:syz

technique:k-近邻算法

优点：精度高，对异常识别不敏感，无数据输入假定

缺点：时间复杂度高，空间复杂度高

适用范围：数值型和标称型

“””

主要思路：

采用欧拉距离运算，取前k个最短距离，然后在这k个距离个数内匹配相应类别的个数，最后取类别个数最高的一个！

import numpy
import operator


def createData():
    group = numpy.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['a', 'a', 'A', 'a']
    return group, labels


def classify_k(inx, dataset, labels, k):
    dataSetSize = len(dataset)
    datasub = numpy.tile(inx, (dataSetSize, 1)) - dataSetSize  # 向量相减
    dataradical = dataset ** 2
    datatotal = dataradical.sum(axis=1)  # 按列求量向量间的平方
    distance = numpy.sqrt(datatotal)  # 求根号
    sort_distance = distance.argsort()  # 依据从小到大，返回对应的索引
    classCount = {}
    for i in range(k):  # 取k次
        votallabel = labels[sort_distance[i]]
        classCount[votallabel] = classCount.get(votallabel, 0) + 1  # 计算出现目标标签的数量
    sortedclass = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)  # 迭代倒序返回字典
    return sortedclass[0][0]


def autoNum(dataset):
    minvals = dataset.min(0)
    maxvals = dataset.max(0)
    range = maxvals - minvals
    zerodata = numpy.zeros(shape=numpy.shape(dataset))
    m = dataset.shape(0)
    # 利用当前数减去最小数，然后除以范围，进行归一
    zerodata = dataset - numpy.tile(minvals, (m, 1))
    zerodata = zerodata / numpy.tile(range, (m, 1))
    return zerodata, range, minvals