集体编程智慧(2)

随机搜索：

该方法接受两个参数，Domain和costf，其中Domain是一个由二元组构成的列表，指定了每个变量的最大最小值。而costf胃成本函数，为其他优化问题所重用，它会跟踪最佳猜测（即具有最低成本的题解）并将结果返回。

本质：随机选择出一些题解，并进行尝试，比较得出尝试解中的最佳值，但不一定是问题的全局最优值。

爬山法：以一个随机解开始，然后在其接近的解集中寻找更好的题解。

缺陷：简单的从斜坡滑下不一定会产生全局最优解。有可能最后的解会是一个局部范围内的最小值，它比临近解的表现都好，但却不是全局最优的。

改进方法：随机重复爬山法，即让爬山法以多个随机生成的初始解为起点运行若干次，借此希望其中有一个解能够逼近全局的最小值。

模拟退火算法：以一个问题的随机解开始，多次迭代。每一次迭代会随机选中题解中的某个数字，然后朝某个方向变化。算法的关键部分：如果新的成本值更低，则新的题解就会称为当前题解，这和爬山法非常相似。但是如果成本值更高的话，则新的题解仍将可能成为当前题解——避免局部最小值问题。

遗传算法：先随机生成一组解（称为种群），在优化过程中的每一步，算法会计算整个种群的成本函数，从而得到一个有关题解的有序列表。在对题解进行排序之后，一个新的种群（下一代）被创建出来了。首先，我们将当前种群中位于最顶端的题解加入其所在的新种群中。新种群中的余下部分是由修改最优解后形成的全新解所组成的。修改题解的两种方法：

变异：在一个存在解的基础上进行微小的、简单的、随机的改变；

交叉或者配对：选取最优解中的两个解，然后将他们按某种方式进行结合

文档过滤

过滤垃圾信息：

1.基于规则的分类器：使用事先设计好的一组规则，用以指明某条信息是否属于垃圾信息。典型的规则有：英文大写字母的过度使用、与药品相关的单词、过于花哨的HTML用色等。

缺点：规则的正确性与否受垃圾信息的读者和张贴为止的不同而不同；垃圾制造者知道了规则以后，容易绕开过滤器，其行为变得更加隐蔽。

文档和单词：

利用某些特征来对不同的内容项进行分类。文档分类，特征即为文档中的单词。当将单词作为特征时，其假设为：某些单词相对而言更有可能会出现于垃圾信息中。这一假设是大多数垃圾信息过滤器背后所依赖的基本前提。

分类器训练：

通过读取正确答案的样本进行学习。如果分类器掌握的文档机器正确分类的样本越多，其预测的效果也就越好。分类器作用：从极为不确定的状态开始，随着分类器不断了解到哪些特征对于分类而言更为重要，其确定性也在逐渐地增加。

计算概率：

对文档中的单词在每个分类中出现次数进行了统计，那么接下来的工作就是要将其转换成概率。

朴素分类器：求出了指定单词在一篇属于某个分类的文档中出现的概率，就需要有一种方法将各个单词的概率进行组合，从而得出整篇文档属于该分类的概率。

1.朴素贝叶斯分类器：朴素的意思即将要被组合的各个概率是彼此独立的，即一个单词在属于某个指定分类的文档中出现的概率，与其他单词出现在该分类的概率是不相关的。

使用朴素贝叶斯分类器，首先我们需要确定整篇文档属于给定分类的概率。通过将所有的概率相乘，计算出总的概率值。

即的概率已经算出来，而对文档分类，真正需要的是，即对于一篇给定的文档，它属于某个分类的概率是多少？这个可以借助于贝叶斯公式求得：

构造朴素贝叶斯分类器的最后一步是实际判定某个内容项所属的分类。此处最简单的方法，计算被考查内容在每个不同分类中的概率，然后选择概率最大的分类。

同时，各个分类不能同等看待，而且在一些应用中，对于分类器而言，承认不知道答案，要好过判断答案就是概率值稍大一些的分类。为了解决这个问题，我们可以为每个分类定义一个最小阈值。

2.费舍尔方法：朴素贝叶斯方法的一种替代方案，它可以给出非常精确的结果，尤其适合垃圾信息过滤。该方法为文档中的每个特征都求得了分类的概率，然后又将这些概率组合起来，并判断其是否有可能构成一个随机集合。同时还会返回每个分类的概率，这些概率彼此间可以进行比较。

每个特征的分类概率计算值为：

注意这种计算方式与朴素贝叶斯分类中特征分类的概率计算不同，朴素贝叶斯中的计算公式等价于：。

概率值组合：将所有概率相乘起来，然后取自然对数，再将所得结果乘以（-2）.

计算结果特征：如果概率彼此独立且随机分布，则计算结果将满足对数卡方分布。

通过将菲舍尔方法的计算结果传给倒置对数卡方函数，我们将得到一组随机概率中的最大值。

优点：为分类选择临界值时允许更大的灵活性；

缺点：复杂

对树进行训练：

CART（分类回归树）：首先创建一个根结点，然后通过评估表中的所有观测变量，从中选出最合适的变量对数据进行拆分。

基尼不纯度：

将来自集合中的某种结果随机应用于集合中某一数据项的预期误差率。

熵：

集合的无序程度。

区别：熵对于混乱集合的“判罚”往往要更重一些。熵更为普遍。

递归方式构造树：

信息增益：当前熵与两个新群组加权平均后的熵之间的差值。算法会针对每个属性计算相应的信息增益，然后从中选出信息增益最大的属性。算法结束：当熵值最低的一对子集求得的加权平均熵比当前几个的熵要大，针对各种可能结果的计数所得将会被保存下来——拆分结束。

决策树的剪枝：

利用递归的方式来训练决策树存在的问题：决策树变得过度拟合，即它可能变得过于针对训练数据。专门针对训练集所创建出来的分支，其熵值与真实情况相比可能会有所降低，但决策树上的判断条件实际上是完全随意的，因此一颗过度拟合的决策树所给出的答案也许会比实际情况更具特殊性。

措施：

1.当熵减少的数量小雨某个最小值时，我们就停止分支的创建——经常被使用，缺陷是某一次分支的创建并不会令熵降低多少，但是随后创建的分支却会使熵大幅降低；

2.先构造好如前所述的整棵树，然后再尝试消除多余的节点——剪枝，解决措施1出现的问题。

剪枝的过程就是对具有相同父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否会小于某个指定的阈值。如果是，则将这些叶节点合并成一个单一的节点，合并后的新节点包含了所有可能的结果值。

决策树优点：处理缺失数据的能力。如果我们缺失了某些数据，而这些数据是确定分支走向所必需的。那么实际上我们可以选择两个分支都走。不过，此处我们不是平均地统计各分支对应地结果值，而是对其进行加权统计。而如果要走多个分支地话，那么我们可以给每个分支赋予一个权重，其值等于所有位于该分支地其他数据行所占地比重。

处理数值型结果：

对于数值型结果，我们可以使用方差作为评价函数来取代熵或者基尼不纯度。较低地方差代表数字彼此都非常地接近，而偏高地方差则意味着数字分散得很开。当使用方差作为评价函数来构造决策树时，我们选择节点判断条件得就变成了：拆分之后令数字较大者位于树得一侧，而数字较小者位于树得另一侧，这样来降低分支得整体方差。

决策树得使用有一个显著得缺陷：我们必须建立大量得价格数据才行，这是因为住房得价格千差万别，而且为了能够得出有价值得结论，我们需要以某种方式对其进行有效得分组。

利用多种不同属性对数值型数据进行预测时，贝叶斯分类器、决策树，以及支持向量机都不是最佳的方法。

在一个拥有众多买家和卖家的大型市场中，通常对于交易双方而言，商品的价格最终将会达到一个最优值。而对于只有一个卖家和多个买家的情况或者只有一个买家和多个卖家的情况，商品的价格都是一个非最优值。美丽心灵中john nash对于一个美女和多个男子之间的约会结果就是没有一个男子能够约到此美女。