机器学习之K近邻算法


概述

AI不断的火起来了,作为工程化的码农,也得奔向国际化轨道了。至于机器学习是什么,不知道找百科。现在大多数机器学习都是采用监督学习形式。我们学习一下KNN算法

KNN

KNN(K近邻)算法属于监督学习的分类问题,采用不同feature之间的距离方法进行分类。 1.优点:精度高、对异常值不敏感、无数据输入规定,不需要训练算法。 2.缺点:计算复杂度和空间复杂度高。 3.原理:依据训练样本集中的每个数据对应一个标签,每个数据集中每一个数据与分类一一对应关系,输入没有标签的数据后KNN算法将新数据的每个特征与样本集中数据对应的特征进行比较,然后提出样本集中特征醉相思的数据的分类标签。比如:依据花瓣、花蕊等features标记的类,对输入的测试数据进行最佳匹配。或者依据打斗镜头、接吻镜头等Features将电影分为爱情片、动作片等。

Demo

标量文本数字的KNN

比如对一个约会网站寻找自己的最适合的约会对象,比如将约会的人分类为:

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

周一至周五我一般会选择魅力一般的人,周末选择极具魅力的人。我手中大约有1000多个约会对象,每个约会对象具有以下三个特征

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

我要将1000多个对象依据这三个features分为上述三类人。下面请看具体的流程

准备数据

数据是在<机器学习实战>中datingTestSet.txt,由于”每年飞行常客里程数”是一个非常大的整数,且”玩视频游戏时间百分比”和”每周消费的冰淇淋公升数”是一个非常小的数值,如果不经过归一化处理之后那么相似性的判断上主要取决于”每年飞行常客里程数”,所以需要经过归一化处理。每个特征的贡献度都是一样的,所以需要将每个特征值进行归一化处理。归一化处理有以下几部分: 0-1归一化,将数据映射到[0-1]范围内。

x^*=\frac{x-min}{max-min}

0-均值规范化(标准差标准化),经过处理的数据的均值为0,标准差为1.

x^*=\frac{x_i-x}{\sigma}

小数定标准规范化

x^*=\frac{x}{10^k}

import pandas as pd
data = pd.read(file)
#0-1归一化
t1=(data-data.min())/(data.max()-data.min())
#0-均值标准化
t2=(data-data.mean())/data.std()
#小数定标规范化
t3=data/10**np.ceil(np.log10(data.abs().max()))

我们看一下测试数据中的数据的格式,然后将“每年飞行常客里程数”0-1归一化,然后数据的格式进行处理即可。

# [每年飞行常客里程数 玩视频游戏时间百分比 每周消费的冰淇淋公升数 样本分类]
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
72993	10.141740	1.032955	1
35948	6.830792	1.213192	3
42666	13.276369	0.543880	3
67497	8.631577	0.749278	1

pandas走起,代码如下:

test = pd.read_table('./datingTestSet2.txt',names=['year','game','ice','class'])
In [99]: test[:3]
Out[99]:
    year      game       ice  class
0  40920  8.326976  0.953952      3
1  14488  7.153469  1.673904      2
2  26052  1.441871  0.805124      1
#归一化处理
In [102]: f = lambda x:(((x-x.min())/(x.max()-x.min())) if x.name!='class' else x)
In [103]: test=test.apply(f)
In [104]: test[:3]
Out[104]:
       year      game       ice  class
0  0.448325  0.398051  0.562334      3
1  0.158733  0.341955  0.987244      2
2  0.285429  0.068925  0.474496      1

下面我们来看一下完整的书写代码的两种方式第一种采用DataFrame结构,第二种采用numpy的array结构。

def class_knn(x,data,label,k=1):
	 #归一化处理函数
    f = lambda x:(x-x.min())/(x.max()-x.min())
    #构造一个数据集,并对数据采用同样的归一化
    test = (DataFrame(x,index=data.index) - data.min())/(data.max()-data.min())
    data = data.apply(f)
    diff = ((test-data)**2).sum(axis=1)**0.5
    indexs = diff.sort_values(axis=0,ascending=True)[:k].index
    return label[indexs].values

if __name__ == "__main__":
    test = pd.read_table('datingTestSet2.txt',names=['year','game','ice','class'])
    data,label = test.ix[:,['year','game','ice']],test['class']
    x = {'year':10000,'ice':0.5,'game':10}
    print class_knn(x, data, label)

第二种,也就是机器学习实战中的代码片段。

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()     
    classCount={}          
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    print sortedClassCount
    return sortedClassCount[0][0]
 
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))   #element wise divide
    return normDataSet, ranges, minVals
# 文件转矩阵处理函数
def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(unicode(listFromLine[-1])))
        index += 1
    return returnMat,classLabelVector

你也可以对数据进行分析和可视化,由于博主只是学习算法的思想。对于计算相似性,不仅可以采用欧氏距离,还有很多计算相似性的重要方法。比如:Pearson相关系数和Spearman秩相关系数。

参考书籍

《机器学习实战》 《统计学习方法》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码洞

水塘抽样与阶层固化

简单抽样算法就是从固定的n个元素里随机选出k个元素,这样每个元素被选的概率都是平等的k/n。简单抽样是最简单的抽样算法,同样也是使用最为普遍的算法。

9920
来自专栏数说工作室

这是一份开光的课程 |《神经网络》中文字幕版(1.3 & 1.4)

《Neutral Network for Machine Learning》(机器学习中的神经网络)系列课程,是深度学习大神 Geoffrey Hinton 毕...

29870
来自专栏个人分享

最大熵的Java实现

这是一个最大熵的简明Java实现,提供训练与预测接口。训练采用GIS训练算法,附带示例训练集。本文旨在介绍最大熵的原理、分类和实现,不涉及公式推导或其他训练算法...

20130
来自专栏专知

【论文推荐】最新八篇情感分析相关论文—Pair-wise判别器、多模态情感分析、上下文语境、Gated 卷积网络

【导读】专知内容组既昨天推出八篇情感分析(Sentiment Analysis)相关论文,又

21730
来自专栏WOLFRAM

Wolfram 语言的新功能:增强的求导功能

22280
来自专栏钱塘大数据

大数据最核心的关键技术:32个算法

奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutsch...

42890
来自专栏AI2ML人工智能to机器学习

一步一步走向锥规划 - LP

一般来说凸优化(Convex Optimization, CO)中最一般的是锥规划 (Cone Programming, CP) 问题, 前面我们介绍了最简单...

11220
来自专栏量化投资与机器学习

【年度系列】监督学习标签在股市中的应用(代码+书籍)

由于低信噪比和非平稳的价格分布,预测未来股票价格走势是一件十分困难的事。现在流行的机器学习算法通常会给你带来不怎么满意的结果。

22260
来自专栏ATYUN订阅号

GitHub项目:自然语言处理领域的相关干货整理

自然语言处理(NLP)是计算机科学,人工智能,语言学关注计算机和人类(自然)语言之间的相互作用的领域。本文作者为NLP初学者整理了一份庞大的自然语言处理领域的概...

1.2K40
来自专栏yw的数据分析

R语言各种假设检验实例整理(常用)

一、正态分布参数检验 例1. 某种原件的寿命X(以小时计)服从正态分布N(μ, σ)其中μ, σ2均未知。现测得16只元件的寿命如下:           ...

92140

扫码关注云+社区

领取腾讯云代金券