机器学习(周志华) 参考答案 第一章 绪论 1.2

机器学习(周志华) 参考答案 第一章 绪论 1.2

机器学习(周志华西瓜书) 参考答案 总目录

* http://blog.csdn.net/icefire_tyh/article/details/52064910
<http://blog.csdn.net/icefire_tyh/article/details/52064910>
机器学习(周志华) 参考答案 第一章 绪论

* http://blog.csdn.net/icefire_tyh/article/details/52065224
<http://blog.csdn.net/icefire_tyh/article/details/52065224>

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

表1.1包含4个样例，3种属性，假设空间中有3∗4∗4+1=493∗4∗4+1=49
种假设。在不考虑沉余的情况下，最多包含k个合取式来表达假设空间，显然k的最大值是49，每次从中选出k个来组成析合式，共ΣCk49=249ΣC49k=249
种可能。但是其中包含了很多沉余的情况(至少存在一个合取式被剩余的析合式完全包含<空集除外>)。

如果考虑沉余的情况

在这里忽略空集，一个原因是并不是太明白空集是否应该加入析合式，另外就算需要加入，求出了前面48种假设的组合，可以很容易求出加入空集后的组合数(每种可能都可以加上空集，再加上1种空集单独的情况)。
48种假设中：
具体假设：2∗3∗3=182∗3∗3=18种
一个属性泛化假设：2∗3+3∗3+2∗3=212∗3+3∗3+2∗3=21种
两个属性泛化假设：2+3+3=82+3+3=8种
三属性泛化：11种
当k=11时，任选一种假设都可以作为一种没有沉余的假设，共4848种。
k的最大值是1818，当k等于1818时，就是1818种具体属性假设的析取式，共11种。
当k取中间值时，就不好分析了。
一种可行的算法：
由于属性泛化后，一个泛化的假设可以对应多个具体假设。

把所有假设按三属性泛化，二属性泛化，一属性泛化，具体属性排序(这样可以保证排在后面的假设不会包含前面的任何一个假设，所以省略了一些包含判断)，进行循环枚举，按顺序遍历所有假设组合
248248种可能(当然绝大部分都提前结束了，不会是那么夸张的量级，虽然也不低)：

* 使用栈来实现非递归，如果当前假设还有没被析合式所包含的具体假设，则认为可以入栈，并当前栈大小的长度计数加11，并继续扫描。
* 如果当前扫描已经到了最后一个假设，或者所有具体假设已经被全部包含，则退栈。
* 循环结束条件：当最后一个假设作为第一个压入栈的元素时，认为已经遍历结束。
由于一共有1818种具体假设，可以用一个3232位整型(变量为hypos_cur)的后1818位来表示每一个具体假设。用1表示具体假设没被包含，用00
表示具体假设已经被析合式包含。初始的析合式为空，可以设初试值为0X3FFFF0X3FFFF。每个假设也对应一个3232
位整型(假设变量为hypo_const),代表着它所对应了哪些具体假设，如果它包含了某种具体假设，则该位为11。

* 判断析合式是否包含了全部的具体假设：hypos_cur=00。
* 判断该假设是否已经被析合范式包含:用hypo_const与hypos_cur做与运算(结果用hypo_tmp表示)，如果为00
表示已经被包含(判断该假设是否包含了当前的析合式:用hypo_const与hypos_cur做或运算，如果为0X3FFFFF0X3FFFFF
，则认为该假设包含了当前析合式，但由于前面对所有假设做了排序，不可能出现这种情况，所以可以省略该判断)。
* 当某个假设加入析合范式后(入栈)用hypos_cur与hypo_tmp做异或运算，来更改析合式所包含的具体假设。
* 出栈时再次用hypos_cur与hypo_tmp做异或，回到加入该假设前的情况。
* 因为是指数级遍历的算法，所以很慢，我的3代i7笔记本大概算了3分钟。 #include <vector> #include <stack> using
namespace std; //按泛化程度排序，保证排在后面的假设不会不会包含前面的任何一个假设 static const char list[] = { 0
,0,0, 0,0,1,0,0,2,0,0,3,0,1,0,0,2,0,0,3,0,1,0,0,2,0,0, 0,1,1,0,1,2,0,1,3,0,2,1,0
,2,2,0,2,3,0,3,1,0,3,2,0,3,3, 1,0,1,1,0,2,1,0,3,2,0,1,2,0,2,2,0,3, 1,1,0,1,2,0,1
,3,0,2,1,0,2,2,0,2,3,0, 1,1,1,1,1,2,1,1,3,1,2,1,1,2,2,1,2,3,1,3,1,1,3,2,1,3,3, 2
,1,1,2,1,2,2,1,3,2,2,1,2,2,2,2,2,3,2,3,1,2,3,2,2,3,3 }; //用来派生的抽象类 class hypos {
public: virtual int insert(int cur) = 0; }; //单个的假设类 /* hypo_const 假设对应的具体假设集合
*/ class hypo :public hypos { public: hypo(int a, int b, int c) { hypo_const = 0
;vector<char> p[3]; if (a == 0) { p[0].push_back(1); p[0].push_back(2); } else
p[0].push_back(a); if (b == 0) { p[1].push_back(1); p[1].push_back(2); p[1
].push_back(3); } else p[1].push_back(b); if (c == 0) { p[2].push_back(1); p[2
].push_back(2); p[2].push_back(3); } else p[2].push_back(c); for (unsigned int
i =0;i < p[0].size();i++) for (unsigned int j = 0;j < p[1].size();j++) for (
unsigned int k = 0;k < p[2].size();k++) hypo_const |= (1 << (p[0][i] * 9 + p[1
][j] *3 + p[2][k] - 13)); } //判断是否要加入到析合式 如果还有具体假设没被包含，则加入 int insert(int cur) {
return (hypo_const & cur); }; private: int hypo_const; }; //用于压入栈的派生类 用来实现非递归
/* hypo_tmp 记录这个假设入栈时，带入了哪些具体假设，出栈时要还原 ptr 记录入栈时的位置 */ class hypo_ss :public
hypos {public: hypo_ss(int _ptr,int tmp){ hypo_tmp = tmp; ptr = _ptr; } int
insert(int cur) { return 0; }; int hypo_tmp; int ptr; }; //用来循环遍历的类 /* sum
各个长度的析合式各有多少种可能 ss 用来实现非递归的栈 hypos_cur 当前没被包含的具体假设 初始值为0X3FFFF hyposs 48个假设集合 */
class Traversal :public hypos { public: Traversal() { hypos_cur = 0x3ffff; for(
int i=0;i<48;i++) hyposs.push_back(hypo(list[3*i], list[3*i+1], list[3*i+2])); }
//循环顺序遍历的主体 //cur 初试的位置 设为0 int insert(int cur) { //当前指向的位置 int ptr = cur; while
(1) { //退出条件 当最后一个假设作为第一个入栈的元素 表示遍历完成 if (ptr > 47 && !ss.size()) break;
//回退条件 扫描到最后或者所有具体假设都被包含 if (hypos_cur == 0 || ptr>47) { hypo_ss hypo_tmp =
ss.top(); hypos_cur ^= hypo_tmp.hypo_tmp; ptr = hypo_tmp.ptr +1; ss.pop();
continue; } //入栈条件 如果该假设还有未被包含的具体假设 则入栈，并当前栈大小的计数加1 if (int tmp
=hyposs[ptr].insert(hypos_cur)) { hypos_cur ^= tmp; ss.push(hypo_ss(ptr, tmp));
if (sum.size() < ss.size()) sum.push_back(0); sum[ss.size() - 1]++; } ptr++; }
return 1; }; //输出各个长度的可能数 void print() { for (unsigned int i = 0;i <
sum.size();i++)printf("length %d : %d\n", i + 1, sum[i]); } private: vector<int>
sum;stack<hypo_ss> ss; int hypos_cur; vector<hypo> hyposs; }; int main() {
Traversal traversal; traversal.insert(0); traversal.print(); system("pause");
return 0; } /* 最终输出: length 1 : 48 length 2 : 931 length 3 : 10332 length 4 :
72358 length 5 : 342057 length 6 : 1141603 length 7 : 2773332 length 8 :
4971915 length 9 : 6543060 length 10 : 6175660 length 11 : 4003914 length 12 :
1676233 length 13 : 422676 length 14 : 61884 length 15 : 5346 length 16 : 435
length 17 : 27 length 18 : 1 */

• « 上一篇：关于前端解决post跨域的问题
• » 下一篇：ubuntu开启守护进程，运行后台php服务（开机启动）