精通数据科学算法

版权信息

书名：精通数据科学算法

ISBN：978-7-115-49816-8

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

著　　　　[英] 戴维•纳蒂加（David Natingga）

译　　　　封　强　赵运枫　范东来

责任编辑　武晓燕

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315

版权声明

Copyright ©2017 Packt Publishing. First published in the English language under the title Data Science Algorithms in a Week.

All rights reserved.

本书由英国Packt Publishing公司授权人民邮电出版社出版。未经出版者书面许可，对本书的任何部分不得以任何方式或任何手段复制和传播。

版权所有，侵权必究。

内容提要

数据科学（Data Science）是从数据中提取知识的技术，是一门有关机器学习、统计学与数据挖掘的交叉学科。数据科学包含了多种领域的不同元素，包括信号处理、数学、概率模型技术和理论、计算机编程、统计学等。

本书讲解了7种重要的数据分析方法，它们分别是k最近邻算法、朴素贝叶斯算法、决策树、随机森林、k-means聚类、回归分析以及时间序列分析。全书共7章，每一章都以一个简单的例子开始，先讲解算法的基本概念与知识，然后通过对案例进行扩展以讲解一些特殊的分析算法。这种方式有益于读者深刻理解算法。

本书适合数据分析人员、机器学习领域的从业人员以及对算法感兴趣的读者阅读。

作者简介

Dávid Natingga于2014年毕业于伦敦帝国理工学院的计算与人工智能专业，并获工程硕士学位。2011年，他在印度班加罗尔的Infosys实验室工作，研究机器学习算法的优化。2012~2013年，他在美国帕罗奥图的Palantir技术公司从事大数据算法的开发工作。2014年，作为英国伦敦Pact Coffee公司的数据科学家，他设计了一种基于顾客口味偏好和咖啡结构的推荐算法。2017年，他在荷兰阿姆斯特丹的TomTom工作，处理导航平台的地图数据。

他是英国利兹大学计算理论专业的博士研究生，研究纯数学如何推进人工智能。2016年，他在日本高等科学技术学院当了8个月的访问学者。

致谢

我很感谢Packt出版社为我提供的这个机会，通过本书分享我在数据科学方面的知识和经验。我由衷地感谢我的妻子Rheslyn，她的耐心、爱与支持贯穿了本书的整个写作过程。

评阅者简介

Surendra Pepakayala是一位经验丰富的技术专家和企业家，在美国和印度有超过19年的工作经验。他在印度和美国的公司担任开发人员、架构师、软件工程经理和产品经理，在构建企业/Web软件产品方面拥有丰富的经验。他同时是一位在企业/Web应用程序开发、云计算、大数据、数据科学、深度学习和人工智能方面具有深厚兴趣和专业知识的技术人员/黑客。

他在美国企业工作了11年之后成为企业家，他成立了一个公司，为美国提供BI/DSS产品。随后他出售了该公司，开始从事云计算、大数据和数据科学咨询业务，帮助初创企业和IT组织简化其开发工作，缩短产品或解决方案的上市时间。此外，Surendra还通过自己丰富的IT经验将亏损的产品/项目变得盈利，他为此感到自豪。

他同时是eTeki（一个按需采访平台）的顾问，他在面试环节的贡献使eTeki在招聘和留住世界级IT专业人员方面处于领先地位。他对CGEIT、CRISC、MSP和TOGAF等各种IT认证草案的修改建议和相关问题进行了审查。他目前的工作重点是将深度学习应用于招聘流程的各个阶段，帮助人事部门（Human Resource，HR）找到最佳人才，并减少招聘过程中的摩擦。

前言

数据科学是一门有关机器学习、统计学与数据挖掘的交叉学科，它的目标是通过算法和统计分析方法从现存数据中获取新知识。在本书中，你将会学习数据科学中7种重要的数据分析方法。每章将首先通过一个简单的例子解释某算法或分析某概念，然后用更多的例子与练习建立与拓展一些特殊的分析
方法。

本书涵盖的内容

第1章，用k最近邻算法解决分类问题，基于 k 个最相似的项对数据项分类。

第2章，朴素贝叶斯，学习用贝叶斯定理来计算某个数据项属于某一个特定类的概率。

第3章，决策树，将决策准则整理、归纳成树的分支，并用一个决策树将数据项分类到叶节点所在的类中。

第4章，随机森林，用决策树集成的方式来划分数据项，通过减少偏差的负面影响来提高算法的准确率。

第5章，k-means聚类，将数据划分成 k 个簇来寻找模式和数据项之间的相似度，并应用这些模式划分新的数据。

第6章，回归分析，通过一个方程对数据进行建模，并以这种简单的方式对未知数据进行预测。

第7章，时间序列分析，通过揭示依赖时间的数据的发展趋势和重复模式来预测未来的股票市场、比特币价格和其他的时间事件。

附录A，统计，提供一个对数据科学家实用的统计方法和分析工具的概要。

附录B，R参考，涉及基本的R语言结构。

附录C，Python 参考，涉及基本的Python语言结构、整本书所用到的命令和函数。

附录D，数据科学中的算法和方法术语，提供数据科学与机器学习领域中一些非常重要并且实用的算法和方法术语。

阅读本书所需要的开发工具

最重要的是，保持一个积极的态度去思考问题——许多新的知识隐藏在练习中。同时，你也需要在自己选择的系统中运行Python和R程序。本书的作者是在Linux操作系统中使用命令行来运行编程语言的。

本书适合的读者

本书是为熟悉 Python 和 R 语言并且有统计背景、期望成为一名数据科学专业人士的读者准备的。那些目前正在开发一两种数据科学算法，并且现在想学习更多的知识以扩展他们技能的开发人员将会发现这本书是非常有用的。

体例约定

本书应用了不同的文本样式以便区别不同种类的信息。这里列举部分的示例并对其含义做出解释。文本中的代码、数据库表名、文件夹名称、文件的扩展名、路径名、虚拟 URL、用户输入和 Twitter 句柄如下所示：“对于这章前面的可视化描述部分，将会用到 matplotlib 库。”

代码块如下所示：

import sys
sys.path.append('..')
sys.path.append('../../common')
import knn # noqa
import common # noqa

任意的命令行输入或者输出如下所示：

$ python knn_to_data.py mary_and_temperature_preferences.data
mary_and_temperature_preferences_completed.data 1 5 30 0 10

　警告信息或者重要注释的标志。

　温馨提示和小技巧的标志。

资源与支持

本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。

配套资源

本书提供如下资源：

• 配套代码。

要获得以上配套资源，请在异步社区本书页面中单击，跳转到下载界面，按提示进行操作即可。注意：为保证购书读者的权益，该操作会给出相关提示，要求输入提取码进行验证。

提交勘误

作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。

当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“提交勘误”，输入勘误信息，单击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。

与我们联系

我们的联系邮箱是contact@epubit.com.cn。

如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。

如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（直接访问www.epubit.com/selfpublish/submission即可）。

如果您是学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。

如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。

关于异步社区和异步图书

“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。

“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近 30 年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。

异步社区

微信服务号

第1章　用k最近邻算法解决分类问题

最近邻算法可以基于某数据实例的邻居来判定该实例的类型。k最近邻算法从距离该实例最近的k个邻居中找出最具代表性的类型，并将其赋给该数据实例。

本章将介绍k-NN算法的基础知识，并通过一个简单的例子——Mary对温度的偏好来理解和实现k-NN算法。在意大利的示例地图上，您将学习如何选择正确的k值，以使算法正确执行并达到最高的准确率。您将从房屋偏好的例子中学习如何重新调整k-NN算法的数值参数。在文本分类的例子中，您将学习如何选择一个好的标准来衡量数据点之间的距离，以及如何消除高维空间中不相关的维度以保证算法的正确执行。

1.1　Mary对温度的感觉　

举个例子，如果Mary在10℃的时候感觉冷，但在25℃的时候感觉热，那么在22℃的房间里，最近邻算法猜测她会感到温暖，因为22℃比10℃更接近25℃。

前面的例子可以知道Mary什么时候感觉到热或冷，但当Mary被问及是否感到热或冷时，风速也是一个影响因素，如表1-1所示。

表1-1

将该数据在图中表示，结果如图1-1所示。

图1-1

现在，假设用1-NN算法判断Mary处在温度为16℃、风速为3km/h情况下的感觉，如图1-2所示。

图1-2

简单起见，这里使用曼哈顿距离来度量网格上邻居节点之间的距离。节点N₂=（x₂，y₂）与节点N₁=（x₁，y₁）的曼哈顿距离d-Man定义为d_Man=| x₁ - x₂ | + | y₁ - y₂ |。

现在用邻居间的距离来标记网格，如图1-3所示。看看哪个已知类型的邻居节点最接近目标节点。

图1-3

很明显，最近邻居（类型已知）的温度为15℃（蓝），风速为5km/h。它与目标节点的距离是3个单位，其类型是蓝色的（冷）。最接近的红色（热）邻居与目标节点相距4个单位。由于我们使用的是1邻近算法，所以我们只关注最近的一个邻居，因此目标节点的类型应该是蓝色的（冷）。

将上述过程作用于每个数据点，得到的完整图形如图1-4所示。

图1-4

请注意，有时某个数据点可被两个相同距离的已知类别（20℃和6km/h）隔开。在这种情况下，可以只选择其中一类或忽略这些边界情况。实际结果取决于算法的实现方式。

1.2　实现k最近邻算法　

这里用Python实现k-NN算法来查找Mary的温度偏好。本节的最后还把Mary例子中由k-NN算法生成的数据可视化。完整可编译代码可以在本书提供的源代码中找到。最重要的部分如下：

# source_code/1/mary_and_temperature_preferences/knn_to_data.py
# 将knn算法作用于输入数据
# 假定输入的文本文件通过行来分隔
# 每条数据都包含有温度、风速、类别（冷/热）

import sys
sys.path.append('..')
sys.path.append('../../common') 
import knn # noqa
import common # noqa

# Program start
# E.g. "mary_and_temperature_preferences.data"
input_file = sys.argv[1]
# E.g. "mary_and_temperature_preferences_completed.data"
output_file = sys.argv[2]
k = int(sys.argv[3])
x_from = int(sys.argv[4])
x_to = int(sys.argv[5])
y_from = int(sys.argv[6])
y_to = int(sys.argv[7])

data = common.load_3row_data_to_dic(input_file)
new_data = knn.knn_to_2d_data(data, x_from, x_to, y_from, y_to, k) 
common.save_3row_data_from_dic(output_file, new_data)

# source_code/common/common.py
# ***通用例程与函数的库***
def dic_inc(dic, key):
    if key is None:
        pass
    if dic.get(key, None) is None:
        dic[key] = 1
    else:
        dic[key] = dic[key] + 1

# source_code/1/knn.py
# ***实现knn算法的库***

def info_reset(info):
    info['nbhd_count'] = 0
    info['class_count'] = {}

# 通过坐标x、y找到邻居的类型（假如该类型是已知的）
def info_add(info, data, x, y):
    group = data.get((x, y), None)
    common.dic_inc(info['class_count'], group)
    info['nbhd_count'] += int(group is not None)
# 将使用曼哈顿距离的k最近邻算法应用于2d数据
# 数据字典的键是2d坐标，值是相应的类型
# x、y是整数2d坐标，其范围为[x_from,x_to]×[y_from,y_to]
def knn_to_2d_data(data, x_from, x_to, y_from, y_to, k):
    new_data = {}
    info = {}
    # 遍历整数坐标系的每个值
    for y in range(y_from, y_to + 1):
        for x in range(x_from, x_to + 1):
    info_reset(info)
    # 从0开始，计算单位距离中每个类组的邻居数，直到至少找到具有已知类的k个邻居
     for dist in range(0, x_to - x_from + y_to - y_from):
         # 计算[x, y]的所有邻居
         if dist == 0:
            info_add(info, data, x, y)
          else:
            for i in range(0, dist + 1):
                info_add(info, data, x - i, y + dist - i)
                info_add(info, data, x + dist - i, y - i)
            for i in range(1, dist):
                info_add(info, data, x + i, y + dist - i)
                info_add(info, data, x - dist + i, y - i)
          # 如果它们到[x，y]的距离是相同的，那么最近的邻居可能多于k个。
          # 当邻居数大于k个时，就从循环中跳出
          if info['nbhd_count'] >= k:
             break
    class_max_count = None
    # 从k个最近的邻居中选择出现次数最多的类型
    for group, count in info['class_count'].items():
        if group is not None and (class_max_count is None or
           count > info['class_count'][class_max_count]):
            class_max_count = group
    new_data[x, y] = class_max_count
return new_data

[输入]

上面的程序将使用下面的文件作为输入数据。该文件包含Mary对温度的已知偏好数据：

# source_code/1/mary_and_temperature_preferences/marry_and_temperature_
preferences.data
10  0  cold
25  0  warm
15  5  cold
20  3  warm
18  7  cold
20  10  cold
22  5  warm
24  6  warm

[输出]

我们在mary_and_temperature_preferences.data这一数据集上执行k =1的k-NN算法。该算法对整数坐标系上的所有数据点进行分类，这一长方形坐标系的范围为(30-5=25)， (10-0=10)，因此总共有(25+1) × (10+1) 即 286个整数点（加一个边界点数）。使用wc命令可以发现输出文件正好包含286行，每个点有一个数据项。使用head命令可以显示输出文件的前10行。下一部分将输出文件中的所有数据可视化：

$ python knn_to_data.py mary_and_temperature_preferences.data mary_and_temperature_preferences_completed.data 1 5 30 0 10

$ wc -l mary_and_temperature_preferences_completed.data 
286 mary_and_temperature_preferences_completed.data

$ head -10 mary_and_temperature_preferences_completed.data
7  3  cold
6  9  cold
12  1  cold
16  6  cold
16  9  cold
14  4  cold
13  4  cold
19  4  warm
18  4  cold
15  1  cold

[可视化]

本章前面所讲的可视化使用了matplotlib库。一个数据文件被加载，然后显示在一个分散的图中：

# source_code/common/common.py
# 返回包含3个list的dict，分别包含x轴、 y轴与颜色数据
def get_x_y_colors(data):
    dic = {}
    dic['x'] = [0] * len(data)
    dic['y'] = [0] * len(data)
    dic['colors'] = [0] * len(data)
    for i in range(0, len(data)):
        dic['x'][i] = data[i][0]
        dic['y'][i] = data[i][1]
        dic['colors'][i] = data[i][2]
    return dic

# source_code/1/mary_and_temperature_preferences/mary_and_temperature_preferences_draw_graph.py 
import sys
sys.path.append('../../common')  # noqa
import common
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
import matplotlib
matplotlib.style.use('ggplot')

data_file_name = 'mary_and_temperature_preferences_completed.data'
temp_from = 5
temp_to = 30
wind_from = 0
wind_to = 10

data = np.loadtxt(open(data_file_name, 'r'),
                    dtype={'names':('temperature','wind', 'perception'), 
                         'formats': ('i4', 'i4', 'S4')})

# 将类转换为在图中显示的颜色
for i in range(0,len(data)):
    if data[i][2] == 'cold':
        data[i][2] = 'blue'
    elif data[i][2] == 'warm':
        data[i][2] = 'red'
    else:
        data[i][2] = 'gray'

# 将数组转换为准备绘制函数的格式
data_processed = common.get_x_y_colors(data)

# 画图
plt.title('Mary and temperature preferences')
plt.xlabel('temperature in C')
plt.ylabel('wind speed in kmph')
plt.axis([temp_from, temp_to, wind_from, wind_to])
# 将图例添加到图表
blue_patch = mpatches.Patch(color='blue', label='cold')
red_patch = mpatches.Patch(color='red', label='warm') 
plt.legend (handles=[blue_patch, red_patch])
plt.scatter(data_processed['x'], data_processed['y'],
            c=data_processed['colors'], s=[1400] * len(data))
plt.show()

1.3　意大利地区的示例——选择k值　

该示例数据集包含了意大利及其周围地区的一些数据点（约1%）。蓝点代表水域，绿点代表陆地，白点代表未知类别。问题是根据已给出的部分信息来预测白色区域是代表水还是土地。

只包含1%地区数据的图片几乎是不见的。假如我们从意大利及周围地区获得大约为之前获得的33倍的数据，并将其绘制在图片中，结果如图1-5所示。

图1-5

[分析]

这里可以使用k-NN算法来解决该问题， k表示算法只关心目标的k个最近邻居。给定一个白点，如果其k个最近邻居大部分都代表水域，则它将被划分为水域；如果其k个最近邻居大部分都代表陆地，则它将被划分为陆地。算法将使用欧几里德距离：给定两个点X = [x₀，x₁]和Y = [ y₀，y₁]，它们的欧几里德距离定义为d= sqrt[(x₀ - y₀)² +(x₁ - y₁)² ]。

欧几里德距离是最常用的距离度量。在一张纸上给出两个点，它们的欧几里德距离就是用尺子测出的长度，如图1-6所示。

图1-6

选择一个k值以将k-NN算法应用于不完整的地区。由于目标点的类别根据其k个最近邻居中出现频次最高的类别来决定，因此k必须是奇数。下面分别将算法的k设为 1、3、5、7、9。

将该算法应用于不完整地区中的每个白点，得到的图如图1-7所示。

图1-7

正如你看到的，k值越高，结果越完整，边界越平滑。完整的意大利地区如图1-8所示。

图1-8

这里可以使用真实的地图来计算错误分类点的百分比，以确定不同k值下k-NN算法的精度，如表1-2所示。

表1-2

因此，对于这一特定类型的分类问题， k-NN算法在k = 1时精度最高（最小误差率）。

但是，现实生活中通常不会有完整的数据集或解决方案供你使用。此时我们需要根据不完整的可用数据来选择适合的k值。更多相关信息请参阅习题1.4。

1.4　房屋所有权——数据转换　

首先给出一份关于部分人的年龄、年收入以及是不是有房子的数据，如表1-3和图1-9所示。

表1-3

其目的是预测50岁、年收入为8万美元的Peter是否拥有房屋，并是否可将其当作保险公司的潜在客户。

图1-9

[分析]

这里可以尝试使用1-NN算法来解决该问题。但是，必须注意数据点之间的距离是如何度量的，因为收入的取值范围比年龄的取值范围宽得多。11.5万美元和11.6万美元相差1000美元。这一收入差异将导致两个数据点拥有很长的距离。但是，相对而言它们的差别其实并不大。由于这两种度量标准（年龄和年收入）都十分重要，因此可以按以下公式将数据缩放至0~1：

缩放量＝（当前量-最小量）/（最大量-最小量）

在该例子中，这等价于：

缩放年龄＝（当前年龄-最小年龄）/（最大年龄-最小年龄）

缩放收入＝（当前收入-最小收入）/（最大收入-最小收入）

缩放之后，得到的数据如表1-4所示。

表1-4

现在，使用1-NN算法与欧几里德度量算法会发现Peter拥有一个房子的可能性更大。请注意，如果不进行缩放，算法会产生不同的结果。参考习题1.5。

1.5　文本分类——使用非欧几里德距离　

现在从信息学和数学的文档中抽取“algorithm”与“computer”关键字，如表1-5所示。

表1-5

在信息学的文档中，“algorithm”与“computer”关键字出现的频率较高。在某些情况下，“algorithm”关键字出现在数学类文档中的频率较高，例如，涉及数论领域中欧几里德算法的文档。但由于数学在算法领域的应用往往比信息学要少，所以“computer”这个词很少出现在数学的文档中。

现在想判断一个文档的类别，其每1000个字包含41个“algorithm”，每1000个字包含42个“computer”，如图1-10所示。

图1-10

[分析]

使用1-NN算法和曼哈顿（Manhattan）或欧几里德（Euclidean）距离将导致这一类别未知的文档被归为数学类。然而，针对这一问题我们应使用不同的距离度量标准，因为该文档比其他数学类的文档拥有更多的“computer”关键字。

此问题的另一个候选度量标准是度量文字计数的比例或文档实例之间的角度。除了角度本身，我们还可以取角度的余弦cos（θ），然后用已知的点积公式来计算cos（θ）。

将a = (a_x, a_y), b = (b_x, b_y)代入公式中：

|a||b|cos(θ)=a . b=a_x . b_x+a_y . b_y

得到：

cos(θ)=

使用余弦距离度量，我们可以将这一类别未知的文档分类为信息类，如图1-11所示。

图1-11

1.6　文本分类——更高维度的k-NN　

假设有一批类别已知的文档，现要根据它们的单词出现频次来区分其他类别未知的文档。例如，在古登堡计划中，某电子书最常用的120个词如表1-6所示。

表1-6

这次的任务是设计一种度量方法，当给定每个文档的单词频率时，该方法可以准确地识别出文档间的相似程度。因此，基于已知类别的文档，k-NN算法可以用这种度量方法对未知类别的新文档进行分类。

[分析]

假设只考虑N个在语料库某文档中出现频率最高的单词。然后计算该文档中这N个单词的出现频次，并将它们放在一个代表该文档的N维向量中。随后将两个文档间的距离定义为代表这些文档的两个词频矢量间的距离（例如欧几里德）。

这个解决方案的问题在于，只有一部分单词能反应书本的实际内容，而其他单词是由于语法规则或其基本含义而存在于文本中的。例如，在该电子书中最常用的120个单词中，每个单词的重要性都不相同，这里突出显示该电子书中出现频率特别高且具有重要意义的单词，如表1-7所示。

表1-7

这些词不太可能出现在数学类文本中，但更可能出现在有关宗教的文本中。

但是，如果我们只看该电子书中最常见的6个词，如表1-8所示，那么它们就不能有效反映文本的含义。

表1-8

上面这批单词在数学、文学或其他学科有关的文本中都具有相似的词频。其间的差异可能主要来自写作风格的不同。

因此，为了确定两个文档之间的相似距离，只需要关注重要单词的出现频次即可。我们应尽量减少其他无关紧要的单词对最终分类结果的影响。现在要做的就是选择重要的单词（维度）来对语料库中的文档进行分类。请参考习题1.6。

1.7　小结　

k最近邻算法是一种分类算法，该算法从距离某数据点最近的k个邻居中找出最具代表性的类型，并将其赋给该数据点。两点之间的距离用某种方式来度量。距离的度量方式包括：欧几里德距离、曼哈顿距离、闵可夫斯基距离、汉明距离、马氏距离、谷本距离、杰卡德距离、切线距离和余弦距离。包含各种参数和交叉验证的实验可以帮助确定参数k的值和哪种度量方式应该被使用。

数据点在空间中的维度和位置由其性质所决定。维度越高，k-NN算法的精度可能越低，而消减重要性相同的维度可以提高算法精度。同样，为了进一步提高精度，每个维度的距离应根据维度品质的重要性进行缩放。

1.8　习题　

1．Mary和她对温度的偏好。想象一下，现在知道Mary在-50℃时感到冷，在20℃时感觉到温暖。当温度分别为22℃、15℃、-10℃时，1-NN算法会认为Mary感到冷还是热？这个算法能否正确预测Mary对温度的感觉？如果没有，请给出原因，并说明算法为什么没有给出正确的结果，以及为了使算法的分类效果更好还需要哪些改进。

2．Mary和她对温度的偏好。当k>1时，1-NN算法会比k-NN算法效果更好吗？

3．Mary和她对温度的偏好。更多的数据表明，Mary在17℃时感到温暖，但是在18℃时感觉冷。按照常识，Mary应该在更高的温度时才会感到温暖。能解释一下可能导致数据发生偏差的原因吗？如何改进对数据的分析？是否应该收集一些非温度数据？假设只有温度数据可用，那么基于这样的数据，1-NN算法仍然可以产生较好的结果吗？如何选择k值使k-NN算法产生更好的效果？

4．意大利地图——选择k的值。我们在该问题中使用了意大利的局部地图。但是，假设完整的地图数据不可用，此时不能计算由不同k值导致的算法误差率。如何选择k-NN算法的k值以实现算法精度最大化？

5．房屋所有权。使用与房屋所有权问题有关的部分数据，使用欧几里德度量标准找到Peter最近的邻居：

（a）使用未缩放数据；

（b）使用缩放数据。

（a）与（b）计算得到的邻居是否相同？哪一个邻居拥有房子？

6．文本分类。假设想在古腾堡的语料库中，使用特定度量标准和1-NN算法，找到与某本书（例如圣经）相似的书籍或文档。如何设计两个文档间相似距离的度量标准？

[分析]

1．相对于-50℃而言，8℃更接近20℃。因此，在-8℃时，该算法认为Mary应该感到温暖。但通过常识可知，这很可能是不正确的。在更复杂的例子中，由于缺乏专业知识，人们会被分析结果误导，从而得出错误的结论。但请记住，数据科学家不仅利用数据分析，同时还会利用实质性的专家知识。因此，对问题和数据的深入理解是得出好结论的关键。

该算法进一步会说，在22℃时，Mary会感到温暖。毫无疑问的是，22℃高于20℃，人们会感觉温度更高更温暖。接下来，根据常识来判断对错。算法会认为Mary处于15℃时会感觉温暖，但常识告诉我们这可能是不对的。

应该收集更多的数据使算法产生更好的结果。例如，如果已知Mary在14℃时感到寒冷，那么现有一个非常接近15℃的数据实例，可以更确定地认为Mary在此温度下会感到寒冷。

2．上面处理的数据其实只包含一个维度，可被分为寒冷和温暖两类，并具有以下特性：环境温度越高，人感觉越暖和。即使知道Mary在-40℃、 -39℃、 ……、 39℃、 40℃的温度下的感受，但数据实例仍然非常有限——每摄氏度只有一个值。出于这些原因，我们最好只关注一个最近的邻居。

3．数据的差异可能是由实验偏差导致的。这可以通过多次实验来缓解。

除了偏好之外，还有一些其他因素会影响到Mary的感受：比如风速、湿度、阳光。无论在潮湿或干燥的环境中，如果Mary穿上牛仔裤，只穿无袖上衣或者一件泳衣，那么她会觉得非常温暖。把一些额外的维度（风速和穿着方式）添加到代表数据点的向量中，会为算法提供更多、更好的数据。因此，算法也可以取得比预期更好的结果。

如果只有温度数据，但数据量较多（例如，每摄氏度有10个已知类别的数据实例），那么可以增加k值并且基于更多的邻居来提高算法精度，而这完全依赖于数据的可用性。这里可以对算法进行修改，使其基于某个数据点一定距离内的所有邻居来区分该数据点的类别，而不是只看k个最近邻居。如果在短距离内有大量数据，即使只有一个类别已知的数据实例靠近类别未知的实例，修改后的算法也能正常工作。

4．为此可以使用交叉验证（请参考附录A中的统计交叉验证部分）确定使算法达到最高精度的k值。可将意大利部分地区的可用数据分为测试集和训练集。例如，将地图上80%类别已知的像素作为k-NN算法的训练集，以完善整个地图。然后，将地图中剩余的20%作为测试集，以计算通过k-NN算法得出的具有正确分类的像素百分比。

5．（a）使用未缩放数据，距Peter最近的邻居，其年收入为7.8万美元，年龄为25岁。这个邻居没有房子。

（b）使用缩放数据，距Peter最近的邻居，其年收入6万美元，年龄40岁。这个邻居拥有房子。

6．为了设计一种能精确测量两个文档间相似距离的度量，我们必须选择重要词汇以形成文档频率向量的各个维度。对于那些不能确定文档语义的单词，它们往往在所有文档中都具有大致相似的出现频次。因此，我们可以生成一个文档中单词的相对频次列表。例如，可以使用如下定义：

relative_frequency_coun(word, document) =

然后，一篇文档可用N个具有最高相对出现频次的单词组成的N维向量表示。相对于由N个具有最高频次单词组成的向量而言，这种向量由更重要的单词组成。