机器学习_周志华 课后习题答案 第一章 Chapter1

习题1.1

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

由所给出的数据集（训练集）可知，属性3个：色泽、根蒂、敲声，其属性值分别有两个。
以A、B分别代表每个属性的两个属性值，“●”代表取什么值都合适。
那么以上的数据集为：1： AAAY ；4：BBBN

因此，我们可以做出的假设规模为：3x3x3+1=28个。
（类似于三个箱子，每个里面取一个球：C（3,1）*C（3,1）*C（3,1））
PS：在此有必要说明一下，我们做出的所有假设均为：(色泽=’’；根蒂=’’；敲声=’’）是好瓜！

版本空间：即假设空间，所有与训练集一致的假设构成的集合（即：我们不收留与训练集相悖的假设）

AAA满足样例1，且不包含样例4，因此放入假设空间
●●●满足样例1，但包含样例4，因此，剔除

接下来我们要做的就是在我们28个假设中，剔除与训练集（样本1,4）相悖的。
——
Step1: 将每个属性的可能存在的属性排列组合，得到可能存在的28种假设；
Step2: 依次判断每种假设是否包含了所有的正例，否，则直接剔除，是则进行下一步；
Step3: 判断该假设是否包含反例（有一个都不行），是，剔除；否，保留。
Step4: 继续判断下一个假设，重复Step2,3
——
废话不多少，直接上代码：

import re  # 正则表达式


def get_all_hyp(list_attr):
    """"获取所有假设，其中不考虑空集的情况"""
    set_hyp = set()
    for value_attr0 in list_attr[0]:
        for value_attr1 in list_attr[1]:
            for value_attr2 in list_attr[2]:
                x = value_attr0 + value_attr1 + value_attr2
                set_hyp.add(x)
    return set_hyp


def classify(list_ins):
    """划分正反例"""
    positive_class = []
    negative_class = []
    for instance in list_ins:
        ins = instance[0:3]
        if instance[3] is "Y":
            positive_class.append(ins[0:3])
        else:
            negative_class.append(ins[0:3])
    return positive_class, negative_class


def get_version_space(list_ins, set_hyp):
    """
    如果某假设未能包含所有的正例，剔除
    如果某假设包含任何反例，剔除
    """

    p_class, n_class = classify(list_ins)
    delete_items = set()

    for hypothesis in set_hyp:
        for negative in n_class:
            re_hyp_n = re.match(hypothesis, negative)  # 判断两者是否匹配
            if re_hyp_n is None:
                for positive in p_class:
                    re_hyp_p = re.match(hypothesis, positive)
                    if re_hyp_p is None:
                        delete_items.add(hypothesis)
                    else:
                        pass
            else:
                delete_items.add(hypothesis)
    version_space = set_hyp - delete_items
    return version_space
        

def main():
    list_attr = [["A", "B", "."], ["A", "B", "."], ["A", "B", "."]]
    """该程序的局限：仅支持三个属性，但属性值任意，有机会再完善"""
    list_ins = ["AAAY", "BBBN"]
    all_hypothesis = get_all_hyp(list_attr)
    version_space = get_version_space(list_ins, all_hypothesis)
    print(version_space, len(version_space))


if __name__ == "__main__":
    main()

结果：
{‘A●●’, ‘AAA’, ‘AA●’, ‘●A●’, ‘●AA’, ‘●●A’, ‘A●A’} 7

代码可能写的有些罗嗦了，有什么可以改进的，希望大家不吝赐教
PS：在这里你只需要知道在正则表达式中：A●●包含AAA、AAB、A●A、AB●等假设就可以了
正则表达式：https://blog.csdn.net/qq_40273675/article/details/89885192

习题1.2

Q：与使用单个合取式来进行假设表示相比，使用“析合范式”将使得假设空间具有更强的表示能力。若使用最多包含k个合取式的析合范式来表达1.1的西瓜分类问题的假设空间，试估算有多少种可能的假设。

数据集所包含的属性分别为色泽、根蒂、敲声，属性值分别有2、3、3个
关于这个习题1.2，网上流传着两种做法：

一种是以48个假设基础（3x4x4=48，不考虑空集），进行排列组合（C（48，k））得到“析合范式”。
传送门：https://blog.csdn.net/icefire_tyh/article/details/52065626
然后针对得到的排列组合判断是否有冗余情况
例如：(色泽=A)V（色泽=●）与(色泽=●)等价，应在k=2的情况中删除(色泽=A)V（色泽=●）假设
注意：是假设内部存在包含关系，而不是假设之间

另一种则以18种假设为基础，传送门：https://blog.csdn.net/yuzeyuan12/article/details/83113461

本文将使用第一种方法进行计算：
Step1:根据属性与属性值得到48种假设，并进行排列组合C(48，k)> 函数：get_combine_hyps(list_attr, k)
Step2:依次判断每个析合范式是否含有通配符∗：有（如(AA●)），进入下一步；无，该假设不冗余；
Step3:利用正则表达式判断析合范式的其他假设是否被包含（如（AAB）V(AA●)）:是，冗余；否，不冗余；
详细内容见以下代码：

import re
import itertools as it


def get_combine_hyps(list_attr, k):
    # Without Empty set
    list_hyps = []
    for value_attr0 in list_attr[0]:
        for value_attr1 in list_attr[1]:
            for value_attr2 in list_attr[2]:
                x = value_attr0 + value_attr1 + value_attr2
                list_hyps.append(x)
    list_com = list(it.combinations(list_hyps, k))  # 排列组合C48,k
    return list_com


def delete_repeated(list_in):
    list_outer = []
    list_general = []
    flag_repeating = 0

    for com_hyp in list_in:
        """找出每组析合范式中的泛化假设"""
        for a_hyp in com_hyp:
            if "." in a_hyp:
                list_general.append(a_hyp)
            else:
                pass
        """判断泛化假设是否与包含其他假设"""
        if len(list_general) == 0:
            flag_repeating = 1
        else:
            for b_hyp in com_hyp:
                for general in list_general:
                    if general == b_hyp:
                        pass
                    else:
                        hyp_re = re.search(general, b_hyp)
                        if hyp_re is None:
                            flag_repeating = 1
                        else:
                            pass
                list_general = []
        if flag_repeating == 1:
            list_outer.append(com_hyp)
            flag_repeating = 0

    return list_outer


def main(k):
    list_attribute = [["A", "B", "."], ["A", "B", "C", "."], ["A", "B", "C", "."]]
    hypothesis = get_combine_hyps(list_attribute, k)
    if k < 1 or k > 48:
        print("k值必须为小于48的正整数！")
    elif k == 1:
        print(len(hypothesis), hypothesis)
    else:
        hyps = delete_repeated(hypothesis)
        print(len(hyps), hyps)


if __name__ == "__main__":
    main(2)

运行结果：
850 [(‘AAA’, ‘AAB’), (‘AAA’, ‘AAC’), (‘AAA’, ‘ABA’), (‘AAA’, ‘ABB’), (‘AAA’, ‘ABC’)……