随笔 - 51, 文章 - 1, 评论 - 41, 引用 - 0
数据加载中……

K近邻算法

概述

k近邻(k nearest neighbor)算法是一种监督算法,用于分类。它基本思想是计算新实例和训练集元素的**距离**,找出k个最接近的实例(neighbor),统计它们所属分类,次数最多的类别作为新实例的类别。

原理与步骤

监督算法可大致分成两个步骤:训练(train)和分类(classify)。从实现考虑还需要算法初始化过程。

本节的代码为python风格的示意代码,不能直接运行,可运行代码参考zxml。

示意代码

 

class KNearestNeighbor:

    def __init__(...):  pass

    def train(...):     pass

    def classify(...):  pass

训练(train)

理论上k近邻算法不需要训练,可直接使用原始数据进行分类。

归一化

数据的分类的量纲差别较大时,小量纲分类在计算的权重将被削弱。使用归一化消除这种影响。方法如下:

 = (x − xmin)/(xmax − xmin)

预处理

将数据进行某种形式的处理可加快寻找k近邻的速度,常用的处理方式有KD-Tree和Ball-Tree,前者对低维欧氏距离有效,后者对所有距离有效。

示意代码

 

def train(self, X, C):

    '''X,C分别代表实例和类别'''

 

    # 实例数据归一化,并保留数据备份

    (self.X, self.C) = (normalize(X), C.copy())

 

    # 可选,如果需要,则构建KD-Tree()

    self.tree = KDTree()

    self.tree.create(self.X)

分类(classify)

分类的大致步骤:找出k个近邻 和*统计类别的次数* 。 分类的部分处理与训练的处理向对应,如:

  • 训练对数据进行归一化,则分类是也需要归一化。
  • 训练使用如KD-Tree等方式进行处理,则分类使用对应的方法寻找k个近邻。

示意代码

 

def classify(self, x):

 

    _x = normalize(x)                   # 将x归一化

    nearest = self.find_neighbors(_x)   # 找出k个近邻

    freq = frequency(nearests)          # 统计每个类型的次数

    return freq.sorted()[-1]            # 排序后,返回次数最多的类别

 

def find_neighbors(self, x):

    '''寻找与x最接近的k个点'''

 

    if self.tree == None:               # 判断是否使用了kd-tree

        ds = self.distance(x, self.X)   # 计算所有点的距离

        indices = ds.argsort()[0:k]     # 排序后,取前面k个

 

    else:

        indices = self.tree.find_neighbors(x, self.k)

 

    # indices是k个近邻的索引位置

    return self.C[indices]

初始化(init)

初始化需要设置算法参数,如k的值,距离公式。

距离

实例之间的距离一般采用欧氏距离,但不排除使用其它的距离计算方法。欧氏距离:

d = x − y = ((xi − yi)2) ≥ xi − yi

 

def __init__(self, k, distance=euclidean ):

    (self.k, self.distance) = (k, distance)

scikit-learn

下面使用scikit-learn中的k近邻算法分类的例子。

 

import numpy as np

from sklearn import neighbors

 

# 准备数据,分成A B两类。A类在[0,0]附近,B类在[1,1]附近。

X = np.array([[0, 0.1],   [-0.1, 0],

              [0.1, 0.1], [0, 0],

              [1, 1],     [1.1, 1],

              [1, 1.1],   [1.1, 1.1]])

 

C = ['A','A','A','A','B','B','B','B']

 

# 初始化

clf = neighbors.KNeighborsClassifier(n_neighbors=3, weights="uniform")

 

# 训练

clf.fit(X, C)

 

# 分类

c = clf.predict(np.array([[0.9,0.8]]))

print(c)

上面的例子可以将k近邻算法分成三步,初始化、训练和分类。初始化可设置参数,本文涉及到的参数有:

  • n_neighbors: 指参数k
  • weights: 指定数据分类的权重,归一化 是其中的一个方式。
  • algorithm: 该参数可设定使用kd-tree等方法。
  • metric: 距离计算公式

参考资料

posted on 2016-10-28 16:18 lemene 阅读(64) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理