课程笔记第三篇
本课程笔记的课程来源于清华大学深圳研究生院-袁博老师的《数据挖掘：理论与算法》。视频在学堂在线或者b站都有。
第二章第五节-特征选择：
特征选择就是要找出那些数据中好的属性。
熵entropy：
衡量一个系统或者变量的值的不确定性，不确定性越大，熵值越大。
例如，如果男人和女人都是50%的话，这个时候是最不确定一个人的性别的，这个时候的熵值就会很高。
在0.5时熵最高为1，0或者1的时候熵值是最低的。
信息增益information gain：
当你知道一个额外的属性的时候，你对这个系统的不确定性降多少，就叫信息增益，原来的熵减去现在的熵，差值就是信息增益。越大越好，说明这个属性的效能越高，决策树时会用到。
特征属性子集搜索：
暴力列举法；
分支定界法（分支界限法？）：需要有个单调假设（比如某个子集一定比这个子集的子集要好），才能剪枝。
最优列举；但是要注意把最优的属性合一起不一定是最好的属性集（组合爆炸）；
一系列贪婪算法：
A. 序列前向选择( SFS , Sequential Forward Selection )
算法描述：特征子集X从空集开始，每次选择一个特征x加入特征子集X，使得特征函数J( X)最优。简单说就是，每次都选择一个使得评价函数的取值达到更优的特征加入，是一种简单的贪心算法。
算法评价：缺点是只能加入特征而不能去除特征。例如：特征A完全依赖于特征B与C，可以认为如果加入了特征B与C则A就是多余的。假设序列前向选择算法首先将A加入特征集，然后又将B与C加入，那么特征子集中就包含了多余的特征A。
B. 序列后向选择( SBS , Sequential Backward Selection )
算法描述：从特征全集O开始，每次从特征集O中剔除一个特征x，使得剔除特征x后评价函数值达到最优。
算法评价：序列后向选择与序列前向选择正好相反，它的缺点是特征只能去除不能加入。
另外，SFS与SBS都属于贪心算法，容易陷入局部最优值。
一些优化算法（ Optimization Algorithms）：
stimulated annealing 模拟退火；
Tabu Search 禁忌搜索；
genetic algorithm 遗传算法；
#跳脱出局部最优#
