【学习笔记】机器学习西瓜书-第一章课后作业

65 阅读 0 评论 43 点赞

我是靠谱客的博主超级招牌，这篇文章主要介绍【学习笔记】机器学习西瓜书-第一章课后作业，现在分享给大家，希望可以做个参考。

1.1 表1.1若只包含编号为1和4的两个样例，试给出相应的版本空间。

在这里插入图片描述
结果：

复制代码

1
2
3
4
5
6
7
8
1	青绿，蜷缩，浊响
3	青绿，蜷缩，*
7	青绿，*，浊响
9	青绿，*，*
19	*，蜷缩，浊响
21	*，蜷缩，*
25	*，*，浊响

只考虑（色泽=青绿；根蒂=蜷缩；敲声=浊响；好瓜）和（色泽=乌黑；根蒂=稍蜷；敲声=沉闷；坏瓜）两个样例。
具体过程：
（1）首先考虑全部的假设空间，共有333+1（空集）=28种

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
1	青绿，蜷缩，浊响
2	青绿，蜷缩，沉闷
3	青绿，蜷缩，*
4 	青绿，稍蜷，浊响
5 	青绿，稍蜷，沉闷
6 	青绿，稍蜷，*
7 	青绿，*，浊响
8 	青绿，*，沉闷
9 	青绿，*，*
10 	乌黑，蜷缩，浊响
11  乌黑，蜷缩，沉闷
12	乌黑，蜷缩，*
13 	乌黑，稍蜷，浊响
14	乌黑，稍蜷，沉闷
15	乌黑，稍蜷，*
16	乌黑，*，浊响
17	乌黑，*，沉闷
18	乌黑，*，*
19	*，蜷缩，浊响
20	*，蜷缩，沉闷
21	*，蜷缩，*
22	*，稍蜷，浊响
23	*，稍蜷，沉闷
24	*，稍蜷，*
25	*，*，浊响
26	*，*，沉闷
27	*，*，*
28 ∅

（2）删去与正类不一致的假设，然后在此基础上继续删去与反类一致的假设：
对于正类：（色泽=青绿；根蒂=蜷缩；敲声=浊响；好瓜）
删去：2，4-6，8，10-18，20，22-24，26，28
只留下：1，3，7，9，19，21，25，27

对于反类：（色泽=乌黑；根蒂=稍蜷；敲声=沉闷；坏瓜）
删去：27
留下：1，3，7，9，19，21，25
（3）整理得到结果：

复制代码

1
2
3
4
5
6
7
8
1	青绿，蜷缩，浊响
3	青绿，蜷缩，*
7	青绿，*，浊响
9	青绿，*，*
19	*，蜷缩，浊响
21	*，蜷缩，*
25	*，*，浊响

1.2

在这里插入图片描述
解答：
西瓜的色泽有三种可能性（青绿、乌黑、* ），根蒂有四种可能性（蜷缩、稍蜷、硬挺、* ），敲声也有四种可能性（浊响、清脆、沉闷和 * ）。一共有3 * 4 * 4 = 48种可能性。分别是：

基本情况：2 * 3 * 3 = 18
一个属性泛化：2 * 3 + 2 * 3 + 3 * 3 = 21
两个属性泛化：2 + 3 + 3 = 8
三个属性泛化：1

如果不考虑冗余，则有在这里插入图片描述
但是该题要求考虑冗余情况，因此需要先确定k（k指合取式数量）的上限值。显然，k的上限值是18，包含各种基本情况，如果加入其他情况都会造成冗余。因此k的取值范围：[1, 18]。
k=1时，有48种假设；
k=18时，有1种假设；
k=2-17时，需要通过计算机遍历所有组合，然后判断它们是否存在冗余。

首先构造一个18x48的矩阵来表达数据，比如：

复制代码

1
2
3
4
100 000 000 000 000 000 表示（青绿，蜷缩，浊响）

111 111 111 111 111 111 表示 （ * ， * ，*）

用itertools.combinations方法放回所有的排列组合迭代器；
将每一种迭代结果相加(析取运算），存放在一个数组中，该数组的作用相当于一个set，不允许出现重复的元素。
由于这是一种规模是指数级的迭代，当k规模大的时候就跑不动了，该代码只展示到k=4的结果。

具体代码如下：

复制代码

import itertools 
import time
 
 
#将数存储为数组
def method(value):
    # 将字符串变成数字列表，使其具有数字加法运算
    result = []
    for i in range(len(value)):
        result.append(eval(value[i])) #eval()将字符串转成相应的对象
    return result
 
#用类表示编码，并定义重载的运算符 + 为析取
class WMcode:
    val  = ''
    len  = 0
    def __init__(self, strv):
        self.val = method(strv)
    def __add__(self,other):    #析取运算
        strv = [] 
        for i in range(len(self.val)):
            addr = self.val[i]+other.val[i]
            if addr >= 2:
                addr = 1
            strv.append(str(addr))
        return WMcode(strv)
    
#对48中假设进行编码
nodes = [WMcode('100000000000000000'),WMcode('010000000000000000'),WMcode('001000000000000000'),
         WMcode('000100000000000000'),WMcode('000010000000000000'),WMcode('000001000000000000'),
         WMcode('000000100000000000'),WMcode('000000010000000000'),WMcode('000000001000000000'),
         WMcode('000000000100000000'),WMcode('000000000010000000'),WMcode('000000000001000000'),
         WMcode('000000000000100000'),WMcode('000000000000010000'),WMcode('000000000000001000'),
         WMcode('000000000000000100'),WMcode('000000000000000010'),WMcode('000000000000000001'),
         WMcode('100000000100000000'),WMcode('010000000010000000'),WMcode('001000000001000000'),
         WMcode('000100000000100000'),WMcode('000010000000010000'),WMcode('000001000000001000'),
         WMcode('000000100000000100'),WMcode('000000010000000010'),WMcode('000000001000000001'),
         WMcode('111000000000000000'),WMcode('000111000000000000'),WMcode('000000111000000000'),
         WMcode('000000000111000000'),WMcode('000000000000111000'),WMcode('000000000000000111'),
         WMcode('100100100000000000'),WMcode('010010010000000000'),WMcode('001001001000000000'),
         WMcode('000000000100100100'),WMcode('000000000010010010'),WMcode('000000000001001001'),
         WMcode('111000000111000000'),WMcode('000111000000111000'),WMcode('000000111000000111'),
         WMcode('100100100100100100'),WMcode('010010010010010010'),WMcode('001001001001001001'),
         WMcode('111111111000000000'),WMcode('000000000111111111'),WMcode('111111111111111111')]
#           （青绿，蜷缩，浊响） （青绿，稍蜷，浊响） （青绿，硬挺，浊响）
#           （青绿，蜷缩，清脆） （青绿，稍蜷，清脆） （青绿，硬挺，清脆）
#           （青绿，蜷缩，沉闷） （青绿，稍蜷，沉闷） （青绿，硬挺，沉闷）
#           （乌黑，蜷缩，浊响） （乌黑，稍蜷，浊响） （乌黑，硬挺，浊响）
#           （乌黑，蜷缩，清脆） （乌黑，稍蜷，清脆） （乌黑，硬挺，清脆）
#           （乌黑，蜷缩，沉闷） （乌黑，稍蜷，沉闷） （乌黑，硬挺，沉闷）
#           （*，蜷缩，浊响） （*，稍蜷，浊响） （*，硬挺，浊响）
#           （*，蜷缩，清脆） （*，稍蜷，清脆） （*，硬挺，清脆）
#           （*，蜷缩，沉闷） （*，稍蜷，沉闷） （*，硬挺，沉闷）
#           (青绿，*，浊响) （青绿，*，清脆） （青绿，*，沉闷）
#           (乌黑，*，浊响) （乌黑，*，清脆） （乌黑，*，沉闷）
#           (青绿，蜷缩，*) （青绿，稍蜷，*） （青绿，硬挺，*）
#           (乌黑，蜷缩，*) （乌黑，稍蜷，*） （乌黑，硬挺，*）
#           (*,*,浊响) (*,*,清脆) (*,*,沉闷)
#           (*,蜷缩，*) (*,稍蜷,*) (*,硬挺,*)
#           (青绿，*，*) （乌黑，*，*） （*，*，*）

#合取式数量k
for k in [1,2,3,4]:
    #存储最终结果的集合A
    A = []
    time_start=time.time()               #开始计时
    comb = list(itertools.combinations(nodes,k)) # 返回元素为k的所有组合情况的元组
    for i in range(len(comb)):
        WMadd = WMcode('000000000000000000')
        for j in range(k):
            WMadd = WMadd + comb[i][j]
            # k=2时，comb是一个有着1128个元组的列表，每个元组有两个元素
            # comb[0][0]、comb[0][1]是第一种组合情况的两个元素
        for allval in A:                       #若A中已经存在当前假设，则舍去，因为这是亢余
            if WMadd.val == allval.val:	       # 判断是否已经存在		
                break
        else:
            A.append(WMadd)
    time_end=time.time()                 #结束计时
    print("K={},一共有{}组合".format(str(k),str(len(A))))
    print('花费时间',time_end-time_start)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import itertools 
import time
 
 
#将数存储为数组
def method(value):
    # 将字符串变成数字列表，使其具有数字加法运算
    result = []
    for i in range(len(value)):
        result.append(eval(value[i])) #eval()将字符串转成相应的对象
    return result
 
#用类表示编码，并定义重载的运算符 + 为析取
class WMcode:
    val  = ''
    len  = 0
    def __init__(self, strv):
        self.val = method(strv)
    def __add__(self,other):    #析取运算
        strv = [] 
        for i in range(len(self.val)):
            addr = self.val[i]+other.val[i]
            if addr >= 2:
                addr = 1
            strv.append(str(addr))
        return WMcode(strv)
    
#对48中假设进行编码
nodes = [WMcode('100000000000000000'),WMcode('010000000000000000'),WMcode('001000000000000000'),
         WMcode('000100000000000000'),WMcode('000010000000000000'),WMcode('000001000000000000'),
         WMcode('000000100000000000'),WMcode('000000010000000000'),WMcode('000000001000000000'),
         WMcode('000000000100000000'),WMcode('000000000010000000'),WMcode('000000000001000000'),
         WMcode('000000000000100000'),WMcode('000000000000010000'),WMcode('000000000000001000'),
         WMcode('000000000000000100'),WMcode('000000000000000010'),WMcode('000000000000000001'),
         WMcode('100000000100000000'),WMcode('010000000010000000'),WMcode('001000000001000000'),
         WMcode('000100000000100000'),WMcode('000010000000010000'),WMcode('000001000000001000'),
         WMcode('000000100000000100'),WMcode('000000010000000010'),WMcode('000000001000000001'),
         WMcode('111000000000000000'),WMcode('000111000000000000'),WMcode('000000111000000000'),
         WMcode('000000000111000000'),WMcode('000000000000111000'),WMcode('000000000000000111'),
         WMcode('100100100000000000'),WMcode('010010010000000000'),WMcode('001001001000000000'),
         WMcode('000000000100100100'),WMcode('000000000010010010'),WMcode('000000000001001001'),
         WMcode('111000000111000000'),WMcode('000111000000111000'),WMcode('000000111000000111'),
         WMcode('100100100100100100'),WMcode('010010010010010010'),WMcode('001001001001001001'),
         WMcode('111111111000000000'),WMcode('000000000111111111'),WMcode('111111111111111111')]
#           （青绿，蜷缩，浊响） （青绿，稍蜷，浊响） （青绿，硬挺，浊响）
#           （青绿，蜷缩，清脆） （青绿，稍蜷，清脆） （青绿，硬挺，清脆）
#           （青绿，蜷缩，沉闷） （青绿，稍蜷，沉闷） （青绿，硬挺，沉闷）
#           （乌黑，蜷缩，浊响） （乌黑，稍蜷，浊响） （乌黑，硬挺，浊响）
#           （乌黑，蜷缩，清脆） （乌黑，稍蜷，清脆） （乌黑，硬挺，清脆）
#           （乌黑，蜷缩，沉闷） （乌黑，稍蜷，沉闷） （乌黑，硬挺，沉闷）
#           （*，蜷缩，浊响） （*，稍蜷，浊响） （*，硬挺，浊响）
#           （*，蜷缩，清脆） （*，稍蜷，清脆） （*，硬挺，清脆）
#           （*，蜷缩，沉闷） （*，稍蜷，沉闷） （*，硬挺，沉闷）
#           (青绿，*，浊响) （青绿，*，清脆） （青绿，*，沉闷）
#           (乌黑，*，浊响) （乌黑，*，清脆） （乌黑，*，沉闷）
#           (青绿，蜷缩，*) （青绿，稍蜷，*） （青绿，硬挺，*）
#           (乌黑，蜷缩，*) （乌黑，稍蜷，*） （乌黑，硬挺，*）
#           (*,*,浊响) (*,*,清脆) (*,*,沉闷)
#           (*,蜷缩，*) (*,稍蜷,*) (*,硬挺,*)
#           (青绿，*，*) （乌黑，*，*） （*，*，*）

#合取式数量k
for k in [1,2,3,4]:
    #存储最终结果的集合A
    A = []
    time_start=time.time()               #开始计时
    comb = list(itertools.combinations(nodes,k)) # 返回元素为k的所有组合情况的元组
    for i in range(len(comb)):
        WMadd = WMcode('000000000000000000')
        for j in range(k):
            WMadd = WMadd + comb[i][j]
            # k=2时，comb是一个有着1128个元组的列表，每个元组有两个元素
            # comb[0][0]、comb[0][1]是第一种组合情况的两个元素
        for allval in A:                       #若A中已经存在当前假设，则舍去，因为这是亢余
            if WMadd.val == allval.val:	       # 判断是否已经存在		
                break
        else:
            A.append(WMadd)
    time_end=time.time()                 #结束计时
    print("K={},一共有{}组合".format(str(k),str(len(A))))
    print('花费时间',time_end-time_start)

1.3 若数据包含噪声，则假设空间中有可能不存在与所有训练样本都一致的假设（即不存在训练错误为0的假设），在此情形下，试设计一种归纳偏好用于假设选择。

解答：归纳偏好可以认为更看重模型效果的哪一个方面。在这一题中，可以选择最接近训练样本的假设。

1.4

在这里插入图片描述

解答：略（太难了，之后再回来做）

1.5 试述机器学习能在互联网搜索的哪些环节起什么作用。

文档管理器：生成更精准的摘要。本质就是文档摘要的自动生成，涉及深度学习、神经网络、NLP
索引构建器：索引构建已很成熟，但我发现仍有学者将机器学习应用于这部分，主要是用机器学习算法代替标准哈希函数，但效果还不太好[3]。
索引管理器：暂无。
索引检索器：这里涉及查询与文本间的匹配，以及搜索结果的排序，也是直接面向用户的部分。

搜索引擎直接给出搜索的答案：这里用到神经网络，它可以通过分析大量数据从而完成特定的任务，如从相关网页中获取长句子和段落，然后提出有关问题答案的信息。
直接进行图片、视频（等多元数据）的搜索：图片的识别已经是常见的技术了，那直接从视频中提出信息呢？谷歌推出Video Intelligence API，不仅可以从视频中提取特定的信息，还能总结视频的脉络、记录视频中的场景，从而对视频进行准确的分类。
更精准的排序（也可成为「精准营销」的部分）：如使用神经网络、决策树等为基础的网页排序算法：RankNet, LambdaRank 和LambdaMART。2015年，谷歌推出RankBrain，它可以选择最适合当前搜索类型的结果，相当于为每个搜索都提供个性化的算法组合。
对用户行为进行综合分析（如历史搜索数据、点击模式、身份信息等进行结构化信息整合）：更多使用在电子商务的搜索系统中。这在电商网站中的使用，应该是很盛行的，但具体没有调研过。
对话式智能交互搜索：如Baidu的语音搜索、利用Siri进行搜索又或者是Google Assistant等。涉及自然语言处理、知识图谱及神经网络等内容。
对垃圾网站的筛选（模式识别）：这部分可以用Outlier的检测来实现，尤其对以前的标题党，或者以前针对算法进行SEO的网站进行甄别。

参考文章：
[1] https://www.jianshu.com/p/e3e27faa1bba
[2] Python中itertools.combinations()的使用
[3] 机器学习 | 机器学习能在互联网搜索的哪些环节起什么作用