首页 > 分享 > 【机器学习】k

【机器学习】k

KNN概述

k-近邻(kNN, k-NearestNeighbor)算法是一种基本分类与回归方法,这里只讨论分类问题中的 k-近邻算法。

作为一种有监督分类算法,是最简单的机器学习算法之一,顾名思义,其算法主体思想就是根据距离相近的邻居类别,来判定自己的所属类别。算法的前提是需要有一个已被标记类别的训练数据集,通俗理解其计算过程:

给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的 k 个实例,这 k 个实例的多数属于某个类,就把该输入实例分为这个类。

一句话总结:近朱者赤近墨者黑!

K近邻算法的输入为实例的特征向量,对应于特征空间的点;输出为实例的类别,可以取多类。k 近邻算法假设给定一个训练数据集,其中的实例类别已定。分类时,对新的实例,根据其 k 个最近邻的训练实例的类别,通过多数表决等方式进行预测。因此,k近邻算法不具有显式的学习过程。

K近邻算法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”。 k值的选择、距离度量以及分类决策规则是k近邻算法的三个基本要素。

场景举例

电影可以按照题材分类,那么如何区分 动作片 和 爱情片 呢?

动作片:打斗次数更多爱情片:亲吻次数更多

基于电影中的亲吻、打斗出现的次数,使用 k-近邻算法构造程序,就可以自动划分电影的题材类型。

现在根据上面我们得到的样本集中所有电影与未知电影的距离,按照距离递增排序,可以找到 k 个距离最近的电影。 假定 k=3,则三个最靠近的电影依次是, He's Not Really into Dudes 、 Beautiful Woman 和 California Man。 knn 算法按照距离最近的三部电影的类型,决定未知电影的类型,而这三部电影全是爱情片,因此我们判定未知电影是爱情片。

工作原理

计算步骤: 假设有一个带有标签的样本数据集(训练样本集),其中包含每条数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较。 计算新数据与样本数据集中每条数据的距离。对求得的所有距离进行排序(从小到大,越小表示越相似)。取前 k (k 一般小于等于 20 )个样本数据对应的分类标签。求 k 个数据中出现次数最多的分类标签作为新数据的分类。 开发流程: 收集数据:任何方法准备数据:距离计算所需要的数值,最好是结构化的数据格式分析数据:任何方法训练算法:此步骤不适用于 k-近邻算法测试算法:计算错误率使用算法:输入样本数据和结构化的输出结果,然后运行 k-近邻算法判断输入数据分类属于哪个分类,最后对计算出的分类执行后续处理

KNN算法优缺点

1.优点 思想简单,易于理解,易于实现;精度高、对异常值不敏感、无数据输入假定、无需训练特别适合于多分类问题。 2.缺点 懒惰算法,进行分类时计算量大,要扫描全部训练样本计算距离,内存开销大,评分慢;当样本不平衡时,如其中一个类别的样本较大,可能会导致对新样本计算近邻时,大容量样本占大多数,影响分类效果;可解释性较差,无法给出决策树那样的规则。 3.注意问题

K值的设定

K值设置过小会降低分类精度;若设置过大,且测试样本属于训练集中包含数据较少的类,则会增加噪声,降低分类效果。

通常,K值的设定采用交叉检验的方式(以K=1为基准)

经验规则:K一般低于训练样本数的平方根。

优化问题

压缩训练样本;

确定最终的类别时,不是简单的采用投票法,而是进行加权投票,距离越近权重越高。

KNN 项目案例

优化约会网站的配对效果 项目概述

海伦使用约会网站寻找约会对象。经过一段时间之后,她发现曾交往过三种类型的人:

不喜欢的人魅力一般的人极具魅力的人

她希望:

工作日与魅力一般的人约会周末与极具魅力的人约会不喜欢的人则直接排除掉

现在她收集到了一些约会网站未曾记录的数据信息,这更有助于匹配对象的归类。

开发流程 收集数据:提供文本文件准备数据:使用 Python 解析文本文件分析数据:使用 Matplotlib 画二维散点图训练算法:此步骤不适用于 k-近邻算法测试算法:使用海伦提供的部分数据作为测试样本。 测试样本和非测试样本的区别在于: 测试样本是已经完成分类的数据,如果预测分类与实际类别不同,则标记为一个错误。使用算法:产生简单的命令行程序,然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。

1.收集数据

海伦将其约会的对象特征提取出来标记分类,存放在了文本中,主要包含以下 3 种特征:

每年获得的飞行常客里程数      玩视频游戏所耗时间百分比     每周消费的冰淇淋公升数

40920 8.326976 0.953952 3

14488 7.153469 1.673904 2

26052 1.441871 0.805124 1

75136 13.147394 0.428964 1

38344 1.669788 0.134296 1

...

2.准备数据:使用 Python 解析文本文件

将文本记录转换为 NumPy 的解析程序

def file2matrix(filename):

"""

Desc:

导入训练数据

parameters:

filename: 数据文件路径

return:

数据矩阵 returnMat 和对应的类别 classLabelVector

"""

with open(filename) as f:

lines = f.readlines()

row_num = len(lines)

matrix = zeros((row_num, 3))

index = 0

class_label = []

for line in lines:

features = line.strip().split("/t")

matrix[index, :] = features[0:3]

class_label.append(features[-1])

index += 1

return matrix, class_label

3.分析数据

import matplotlib

import matplotlib.pyplot as plt

fig = plt.figure()

ax = fig.add_subplot(111)

ax.scatter(datingDataMat[:, 0], datingDataMat[:, 1], 15.0*array(datingLabels), 15.0*array(datingLabels))

plt.show()

下图中采用矩阵的第一和第二列属性得到很好的展示效果,清晰地标识了三个不同的样本分类区域,具有不同爱好的人其类别区域也不同。

归一化数据

归一化是一个让权重变为统一的过程,更多细节请参考: https://www.zhihu.com/question/19951858 

样本3和样本4的距离:

(0−67)2+(20000−32000)2+(1.1−0.1)2" role="presentation">(0−67)2+(20000−32000)2+(1.1−0.1)2

归一化特征值,消除特征之间量级不同导致的影响

归一化定义: 我是这样认为的,归一化就是要把你需要处理的数据经过处理后(通过某种算法)限制在你需要的一定范围内。首先归一化是为了后面数据处理的方便,其次是保正程序运行时收敛加快。 方法有如下:

1) 线性函数转换,表达式如下:  

y=(x-MinValue)/(MaxValue-MinValue)  

说明:x、y分别为转换前、后的值,MaxValue、MinValue分别为样本的最大值和最小值。  

2) 对数函数转换,表达式如下: 

y=log10(x)  

说明:以10为底的对数函数转换。

如图:

![对数函数图像](http://data.apachecn.org/img/AiLearning/ml/2.KNN/knn_1.png)

3) 反余切函数转换,表达式如下:

y=arctan(x)*2/PI 

如图:

![反余切函数图像](http://data.apachecn.org/img/AiLearning/ml/2.KNN/arctan_arccot.gif)

在统计学中,归一化的具体作用是归纳统一样本的统计分布性。归一化在0-1之间是统计的概率分布,归一化在-1--+1之间是统计的坐标分布。

def normalize(matrix):

"""

Desc:

归一化特征值,消除特征之间量级不同导致的影响

parameter:

dataSet: 数据集

return:

归一化后的数据集 normDataSet. ranges和minVals即最小值与范围,并没有用到

归一化公式:

Y = (X-Xmin)/(Xmax-Xmin)

其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。

"""

min_val = matrix.min()

max_val = matrix.max()

ranges = max_val - min_val

m = matrix.shape[0]

norm_matrix = matrix - tile(min_val, (m, 1))

norm_matrix = norm_matrix / tile(ranges, (m, 1))

return norm_matrix, ranges, min_val

4.训练算法:此步骤不适用于 k-近邻算法

因为测试数据每一次都要与全量的训练数据进行比较,所以这个过程是没有必要的

kNN 算法伪代码:

对于每一个在数据集中的数据点:

计算目标的数据点(需要分类的数据点)与该数据点的距离

将距离排序:从小到大

选取前K个最短距离

选取这K个中最多的分类类别

返回该类别来作为目标数据点的预测值

def classify(input_data, dataset, labels, k):

"""

knn分类算法

:param input_data: 输入待分类的目标数据,即某人的特征一维向量(一行列表)

:param dataset: 分类数据集

:param labels: dataset对应的分类标签

:param k: k个最下距离

:return:

"""

msize = dataset.shape[0]

diff_mat = tile(input_data, (msize, 1)) - dataset

sq_diff_mat = diff_mat ** 2

sq_distances = sq_diff_mat.sum(axis=1)

distances = sq_distances ** 0.5

sorted_index = distances.argsort()

class_count = {}

for i in range(k):

label = labels[sorted_index[i]]

class_count[label] = class_count.get(label, 0) + 1

sorted_class = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)

return sorted_class[0][0]

5.测试算法

使用海伦提供的部分数据作为测试样本。如果预测分类与实际类别不同,则标记为一个错误。

def dating_class_test():

"""

Desc:

对约会网站的测试方法

parameters:

none

return:

错误数

"""

ratio = 0.1

feature_matrix, labels = txt2matrix("data/datingTestSet.txt")

norm_mat, ranges, min_val = normalize(feature_matrix)

m = norm_mat.shape[0]

test_num = int(m * ratio)

error_count = 0

for i in range(test_num):

classifier_result = classify(norm_mat[i, :], norm_mat[test_num:m, :, labels[test_num:m, :, 3]])

print("the classifier came back with: %d, the real answer is: %d" % (classifier_result, labels[i]))

if (classifier_result != labels[i]):

error_count += 1

print("the total error rate is: %f" % (error_count / test_num))

print(error_count)

6.使用算法

产生简单的命令行程序,然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。

约会网站预测函数伪代码

def classifyPerson():

resultList = ['not at all', 'in small doses', 'in large doses']

percentTats = float(raw_input("percentage of time spent playing video games ?"))

ffMiles = float(raw_input("frequent filer miles earned per year?"))

iceCream = float(raw_input("liters of ice cream consumed per year?"))

datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')

normMat, ranges, minVals = autoNorm(datingDataMat)

inArr = array([ffMiles, percentTats, iceCream])

classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels, 3)

print "You will probably like this person: ", resultList[classifierResult - 1]

相关知识

【机器学习】6:K
python机器学习
【机器学习】鸢尾花分类:机器学习领域经典入门项目实战
【机器学习】鸢尾花分类
【机器学习】任务七:聚类算法 (K
机器学习算法
Python机器学习基础教程
机器学习笔记(通俗易懂)
【机器学习】KNN算法实现鸢尾花分类
机器学习案例:鸢尾花分类——基于Scikit

网址: 【机器学习】k https://m.huajiangbk.com/newsview854487.html

所属分类:花卉
上一篇: 科学理性看待转基因技术
下一篇: 可视化=面子工程?浅谈企业可能走