kNN最邻近规则分类

原理介绍:

         这一个月来恶补了一下大学的数学知识,把高数、线代、概率论、复变函数和积分变换又温习了一遍,大学里学的差一点就忘光了。大学时每次上数学课可都是昏昏欲睡啊!哈哈!学习人工智能中关于分类的知识,碰到很多数学描述都看不太懂,才意识到自己的数学在不拾一拾就剩加减乘除了。

         一个同事,也是搞C++ 的,对预测彩票非常感兴趣。我们认为这是个数学问题。做游戏开发,碰到数学问题还真不多,大部分都是逻辑问题,如A打伤了B,B打死了C诸如此类。然后提到如何实现通过程序为人们推荐手机,发现主要也是数学问题。总结来,在日常的软件开发中,主要涉及逻辑控制和数学建模两大部分,为了实现逻辑控制,我们精通编程语法,熟记API,优雅的涉及模块和类,高效的传输和存储数据。是的,这确实已经是很复杂的学问了。但对于我们来说,数学问题更让人着迷。

         其实今天是要记录一下k-NN最近邻规则算法的。最近养成了一个习惯,将一个数学模型掌握以后,应用到一个例子中,并把它用Blog记录下来。K-NN是一种非常朴素的分类算法,但是在步入正题之前,还是要抛个转。

         比如要实现一个模型为人人们推荐购买哪一款手机。为简化模型我们只基于协同过滤做推荐(洒家也是在推荐系统论坛长期潜水之人,常用的推荐策略还是略知一二的)。举个例子,已知A、B二人,A是月薪15k年龄28的帅哥,而B是月薪3K的年龄23的实习生,还知道A购买了Iphone, 而B购买了小米。如果C是月薪13K年龄27,那么你十分有可能和A进行相同的选择,也去购买Iphone。数学上认为C的函数值更解决于A。这就是k-NN最近邻规则的思想,找到和目标属性最接近的样本,并把它们归为同一类别。物以类聚,人以群分嘛。

         如果已知100 个各个收入阶层、各个年龄段的手机购买数据,把其作为训练样本,从中选择一个和目标情况最为接近的一个样本,并把该样本使用的手机推荐给目标,这种分类方法称之为1-NN最近邻规则。进行推广之,从100 人中选出5个最接近目标情况的样本,并把他们使用最多的一款手机推荐给目标,则称之为k-NN最近邻规则,此时k=5。

         设计k-NN最近邻规则时,最重要的是确定k值和设计计算样本之间距离(或相似度)的度量函数。

         首先说计算k值。有时可以根据经验。比如上面推荐手机的例子,k=1 显然不合适,比如月薪20k的大牛可能就喜欢android,非要买个三星也是有的,如果目标和此大牛情况相近就会被推荐三星,但是实际上这一类人大部分都在使用iphone。而若选择5,那么虽然这个大牛使用了三星,但是其他四个人都是使用iphone,那么系统仍然会推荐iphone,这就非常符合现实情况了。但是k值又不能太大,太大计算量增大,并且有可能会出现给一个20k的大牛推荐山寨机的结果。更科学的方法是尝试几种最有可能的k值,计算该k值下的误差率,选择误差率最小k值。

         下面再说一下如何计算两个样本之间的距离,即确定一个度量函数D。任意两个样本a、b,D(a, b) 得到a、b之间的距离。而a样本又有各个属性,数学表示X=(x1, x2,…..)。最简单计算距离的方法是欧几里得公式:

         但是欧几里得法有一个缺陷,若属性的单位发生变化,可能会影响原来各个样本之间的相对距离。如把月薪20k改成月薪20000那么可能会造成原来A更接近于B,但是变成A更接近于C。这里也能说明k值不宜选的太小。

         下面附一个小示例:

已知20个样本:

样本

月收入

年龄

手机

1

2k

18

Iphone6

…….

10

5k

23

小米

……

50

10k

25

Iphone

又已知10个测试样本:

样本

月收入

年龄

手机

1

6k

22

三星

…….

2

9k

25

Iphone

距离度量函数选择欧几里得公式,不同的K值测试的误差对比如下:

K值

1

2

3

4

5

6

7

8

9

误差率

19%

19%

10%

28%

19%

28%

28%

28%

28%

所以选择K值为3,

运行代码如下:

train_data = []
test_data  = []

def init_data():
    f = open("train_data.txt")
    dest = train_data
    for line in f.readlines():
        if len(line) == 0:
            continue
        if line[0] == '#':
            if -1 != line.find('test_data'):
                dest = test_data
            continue
        line_array = line.strip().split()
        if len(line_array) == 3:
            line_array[0] = float(line_array[0])
            line_array[1] = int(line_array[1])
            line_array.append(0)
            dest.append(line_array)
    f.close()

def select_k_neighbour(k, income, age):
    def my_cmp(E1, E2):
        return -cmp(E2[3], E1[3]) 

    distance = []
    for item in train_data:
        income2 = item[0]
        age2    = item[1]
        item[3] = (income - income2) * (income - income2) + (age - age2) * (age - age2)
        distance.append(item)

    distance.sort(my_cmp)
    select_k = {}
    for k in range(0, k):
        phone = distance[k][2]
        if False == select_k.has_key(phone):
            select_k[phone] = 1
        else:
            select_k[phone] = select_k[phone] + 1

    ret_phone = ''
    max       = 0
    for k in select_k:
        if select_k[k] > max:
            max = select_k[k]
            ret_phone = k

    return ret_phone

def knn_train(k):
    right = 0.0
    wrong = 0.0
    for item in test_data:
        income = item[0]
        age    = item[1]
        phone  = item[2]
        ret_phone = select_k_neighbour(k, income, age)
        if ret_phone == phone:
            right = right + 1
        else:
            wrong = wrong + 1
    return right / (right + wrong)

init_data()
print("train_data", train_data)
print("test_data", test_data)

ret = []
for i in range(0, 10):
    rate = 1 - float(int(knn_train(i+1) * 100 )) / 100
    ret.append(str(rate))
print('')
print(ret)

 数据文件为:

# train_data
# income    age     phone
    2       20      N
    3       21      M
    3       22      N
    3.5     22      N
    4       23      M
    4       24      M
    5       24      M
    5.5     25      M
    6       25      M
    7       26      I
    7.5     25      M
    7.5     28      I
    8       27      I
    9       27      I
    10      29      I
    11      28      M
    12      27      I
    13      28      M
    14      30      I
    15      30      I      
    16      30      I
    
# test_data
    2.5     23      N
    3       24      M
    3.5     24      N
    4       25      M
    4.5     26      M
    5.5     26      M
    6       27      I
    7       26      M
    8       28      I
    9       30      I
    12      31      I
    

k-NN 算法的优化:

         很显然的一个问题是k-NN要求遍历所有的训练样本,若训练样本非常庞大,那么计算量可能是不能接受的。针对k-NN算法的优化方法有:

裁剪训练样本

         既然训练样本太多,那么我们就把训练样本比较接近的合并成一项,如月薪10k-12k的统一化为10k之类,减少训练样本数量。

建立搜索树

         思想就是先分几个大类,在再小类中找相似的,如>10k的在某一类别中,那么一次可以淘汰N多不太可能的计算。

属性降维法

         本文中只选择了收入和年龄作为人的属性,实际让远远应比此大的多的多,在遍历训练样本时,可以从中选择有代表性的属性用于计算,或者可以通过变换减少属性。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SIGAI学习与实践平台

理解计算:从√2到AlphaGo ——第1季 从√2谈起

计算的概念看似简单却又十分宽泛,它实际上是计算机学科永远不变的核心内容,就算现在所谓的人工智能,在我看来也不过是一种计算或计算结果的应用。本文将从简单的例子出发...

983
来自专栏AI科技评论

干货 | 清华大学冯建江:指纹识别现状与研究进展

AI 科技评论按:2018 年 4 月 14 日-15 日,中国图象图形学学会围绕「生物特征识别」这一主题,在中科院自动化所举办第四期「CSIG 图像图形学科前...

1944
来自专栏机器之心

百度NLP | 神经网络语义匹配技术

百度NLP专栏 作者:百度NLP 一、序言 文本匹配是自然语言处理中一个重要的基础问题,自然语言处理中的许多任务都可以抽象为文本匹配任务。例如网页搜索可抽象为网...

5367
来自专栏新智元

当贝叶斯,奥卡姆和香农一起来定义机器学习

令人有点惊讶的是,在所有机器学习的流行词汇中,我们很少听到一个将统计学、信息理论和自然哲学的一些核心概念融合起来的短语。

1193
来自专栏机器之心

学界 | 为给定任务自动生成神经网络:MIT提出RNN架构生成新方法

28110
来自专栏专知

【AAAI2018】预测你的下一步-动态网络节点表示学习,浙江大学和南加州大学团队工作,代码已开源

【导读】以往的网络表示学习模型只会为固定的网络节点学习表示向量,而实际上,网络节点会根据时间的变化通过节点间的交互呈现出不同的网络结构特性。浙江大学和南加州大学...

4088
来自专栏磐创AI技术团队的专栏

【干货】二十五个深度学习相关公开数据集

(选自Analytics Vidhya;作者:Pranav Dar;磐石编译) 目录 介绍 图像处理相关数据集 自然语言处理相关数据集 语音处理相关数据集 ...

3285
来自专栏数据科学与人工智能

【知识】人工智能数学基础知识

数学是打开科学大门的钥匙。——培根 数学基础知识蕴含着处理智能问题的基本思想与方法,也是理解复杂算法的必备要素。今天的种种人工智能技术归根到底都建立在数学模型之...

2527
来自专栏CDA数据分析师

怎样入手学习R的算法?

文 | 陆勤 来源 | 数据人网 R是目前学习R语言中应用最广泛的平台。当你认真起来学习R的时候你会找到学习R的窍门。 它之所以功能强大是因为很多机器学习的算法...

2019
来自专栏黄成甲

数据分析之描述性分析

1.描述性分析主要是对所收集的数据进行分析,得出反映客观现象的各种数量特征的一种分析方法,它包括数据的集中趋势分析、数据离散程度分析、数据的频数分布分析等,描述...

2752

扫码关注云+社区