kNN算法

理想环境下的kNN

---

计算距离 ->取最近的K个值 -> 选取占比高的类别

1. 计算距离

原始数据:9条数据,2个属性,2个类别

对于待分类的点**(61,20) **, 可以得到对于每个点的距离,使用曼哈顿距离公式.我不是为了偷懒,就是用这个

项目	X1	X2	X3	X4	X5	X6	X7	X8	X9
距离	11	20	6	14	3	81	68	86	71
类别	A	A	A	A	B	B	B	B	B

2. 最近k个

最近的三个依次是X5-B,X3-A,X1-A

3. 判断类别

A占66%,B占33%
所以待分类点**(61,20) **是A类别

4. 简单py实现

计算机负责计算,可以舍弃曼哈顿距离了,用最经典的欧几里得距离

# -*- coding: utf-8 -*-

__author__ = 'Matter-YYF'

from numpy import *
import operator

def createDataSet():
    # numpy的array可以初始化矩阵
    group = array([[50.0,20.0],[53.0,32.0],[60.0,25.0],
                  [65.0,30.0],[58.0,20.0],[10.0,50.0],
                  [20.0,47.0],[15.0,60.0],[25.0,55.0]])
    label = ['A','A','A','A','B','B','B','B','B',]
    return group,label

def classify0(inX, dataSet, labels, k):
    # shape属性是行列数
    dataSetSize = dataSet.shape[0]
    # 用tile创建重复数组,此处用于创建矩阵 tile([61.0,20.0],(9,1))
    diffMat = tile(inX,(dataSetSize,1))-dataSet

    sqDiffMat = diffMat ** 2
    # 矩阵每行相加
    sqDistance = sqDiffMat.sum(axis=1)
    distance = sqDistance ** 0.5
    # 字典key排序
    sortedDistIndex = distance.argsort()
    classCount = {}
    for i in range(k):
        voteLabel = labels[sortedDistIndex[i]]
        # XX.get(a,b):有key=a的则取对应value,没有则为b
        classCount[voteLabel] = classCount.get(voteLabel,0)+1
    # 前k个类别的排序
    sortedClassCount = sorted(classCount.iteritems(),
                              key=operator.itemgetter(1),
                              reverse=True)
    # 返回占比例最高的类别
    return sortedClassCount[0][0]

dataSet,label = createDataSet()
resultKNN = classify0([61.0,20.0],dataSet,label,3)
print resultKNN

欢迎回到现实世界

---

1. 手输数据是有多蛋疼...

劳资是程序猿,不干low活

得从文件读数据啊

def file2matrix(filename):
    fr = open(filename)
    arrayOfLines = fr.readlines()
    numberOfLines = len(arrayOfLines)
    returnMat = zeros((numberOfLines,3))    # 生成一个空白矩阵,3列
    classLabelVector = []
    index = 0
    for line in arrayOfLines:
        line = line.strip()                 # 删除空白符:'\n','\r','\t',' '
        listFromLine = line.split('\t')     # 以制表符为分割生成列表
        returnMat[index,:] = listFromLine[0:3]              # 前三个项目是数据属性
        classLabelVector.append(int(listFromLine[-1]))      # 最后是类别标签
        index+=1
    return returnMat, classLabelVector

2. 数据怎么跨度这么大...

10w和25在一起,好别扭

归归归归一化

线性函数归一化(Min-Max scaling)

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))    #计算结果
    return normDataSet, ranges, minVals