《机器学习》第15章习题

15.1

首先对于书76页的西瓜数据集进行了处理，将所有的属性：色泽、根蒂、敲声、纹理、脐部和触感分别以数字0,1,2,3,4,5,6，对于这7个属性的属性值，按照程度以1,2,3取值，比如色泽属性的值浅白=1，青緑=2，乌黑=3，具体见表：

按照这种方式西瓜数据表2.0按照顺序可表示为：

static int[][] watermelon = {
            {2, 3, 2, 1, 3, 1},
            {3, 3, 3, 1, 3, 1},
            {3, 3, 2, 1, 3, 1},
            {2, 3, 3, 1, 3, 1},
            {1, 3, 2, 1, 3, 1},
            {2, 2, 2, 1, 2, 2},
            {3, 2, 2, 2, 2, 2},
            {3, 2, 2, 1, 2, 1},
            {3, 2, 3, 2, 2, 1},
            {2, 1, 1, 1, 1, 2},
            {1, 1, 1, 3, 1, 1},
            {1, 3, 2, 3, 1, 2},
            {2, 2, 2, 2, 3, 1},
            {1, 2, 3, 2, 3, 1},
            {3, 2, 2, 1, 2, 2},
            {1, 3, 2, 3, 1, 1},
            {2, 3, 3, 2, 2, 1}
    };

同时，属性取值可以表示为：

static int[][] ruleMatric = {
            {1, 2, 3}, 
            {1, 2, 3}, 
            {1, 2, 3}, 
            {1, 2, 3}, 
            {1, 2, 3}, 
            {1, 2, 3}
    };

实现方法是按照书上来的，对于找到的规则，只要满足只覆盖正例就将此规则存储起来，并且不再针对此规则加命题。
代码见Github，这里没有使用否定形式的命题，也没有加入beam；在搜索规则时做了两个剪枝：

1. 对于一条规则，已经加入的属性不再尝试，这复合常理，比如取了色泽=青緑，下一步再去看色泽是没有意义的。代码中使用了List<RuleUsed> ruleUsedList来进行记录。
2. 举例说明： 第一轮我取了色泽=青緑（因为这个属性得到的正例比例最高），然后对其继续搜索，当得到满足条件的规则后，由于并不是所有的正例都被覆盖，就需要去看第一轮中正例比例第二高的属性继续去搜索，这里取根蒂=蜷缩，在对根蒂=蜷缩这条规则的后续搜索中，永远都不会再考虑色泽=青緑这个属性-值对，因为对色泽=青緑后续搜索过程中，已经有过（色泽=青緑，根蒂=蜷缩）这样的组合了。代码中使用了List<RuleUsed> repeatedRuleList来进行记录。

得到的规则是：（31,01），（31,13），（31,51），（31,22,02），（03,22,32）。
每一个规则覆盖的西瓜分别是：（4），（0,1,2,3），（7），（5），（6）。

15.2

自底向上的方法我是这样考虑的，书中并没明确自底向上的方法要得到什么样的规则，是最短的还是覆盖样例最多总规则数量最少，都没有说明，我这里明确将要得到的目标规则为：优先覆盖正例最多，然后最短，允许出现重复覆盖，但每条规则要至少有一个样例是它唯一覆盖的，其他随意。
同时，我只考虑了命题的删除，没有考虑命题的替换，因为我认为命题的替换没有意义，替换一个命题后，这条规则原来覆盖的正例肯定就不覆盖了，如果这条规则又覆盖了更多个别的正例后，我认为这个操作才是有意义的，但是在自底向下的方法中覆盖别的正例是可以通过这个正例的初始规则删减得到的，尽管可能无法得到最优结果，比如要总规则数量最少，但只考虑删除实现复杂度和代码运行复杂度都较低而且也能得到不错结果，所以我只考虑了命题的删除。
具体算法为：

1. 取一个正例的文字描述为初始规则，记录这条规则。
2. 当前规则内有n个命题，依次删去一个命题，生成n条有n-1个命题的规则，
3. 对新生成的规则，保留只覆盖正例的规则，并记录它们。
4. 对3中保留的规则，若数量为0，回到1，否则对每一保留的规则进行2。
5. 对所有保留规则按照 覆盖正例数量(越多越好) > 规则长度(越短越好)排序，然后依次取出规则，若至少有一个正例被这个规则唯一覆盖，则保留这条规则，知道所有正例都被覆盖，输出保留的规则。

代码见Github。实现过程中也做了和15.1类似的剪枝操作。

得到的规则是：（31,51），（02,22,31），（32,52）。
每一个规则覆盖的西瓜分别是：（0,1,2,3,4,7），（0,5），（6）。