Boosting（提升）方法是一种常用的统计学习方法，其中最具有代表性的算法是AdaBoost。AdaBoost起源于PAC可学习性（probably approximately correct learnability）的研究。历史上，Valiant和Kearns首先提出了强可学习（strongly learnable）和弱可学习（weakly learnable）。在PAC框架下，若一个算法的识别准确率很高并能在多项式时间内完成则为强可学习；若一个算法的错误率仅仅比随机猜测略低，则称之为弱可学习。后来Schapire证明强可学习和弱可学习是等价的：在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。如此，问题就变成了：如果已经发现了一个弱学习算法，是否能够将其提升（boosting）为一个强学习算法。

关于提升方法的研究很多，例如：boostrapping，将多个弱分类器分配不同的权值来组成强分类器；bagging，根据多个弱分类器的投票结果来确定最后的分类结果。这些提升方法中，最有效最具有代表性的则是AdaBoost。

AdaBoost算法过程

AdaBoost通过每一轮的分类结果来改变每个样本的权值，使得分类错误的样本权值变大，分类正确的样本权值变小，这样使得没有正确分类的数据获得更高的关注。对于多个弱分类器，AdaBoost通过加权多数表决来组合，误差率小的分类器权值大，反之，则权值小。具体算法如下：

1. 初始化训练数据的权值分布
   $D_1=(w_{11},w_{12},..,w_{1N}), {w_{iN}={1\over N}}, i=1,2,..,N$
2. 对m=1, 2, .., M
   1. 使用具有权值 $D_m$ 的训练数据集学习，得到基本分类器 $G_m(x)$
   2. 计算 $G_m(x)$ 在数据集上的分类误差率， $e_m=P(G_m(x_i)\neq y_i)=\sum_i^N{w_{mi}I(G_m(x_i)\neq y_i)}$
   3. 计算 $G_m(x)$ 的系数 $\alpha_m={1\over 2}ln{{1-e_m}\over e_m}$
   4. 更新数据集的权值分布 $D_{m+1}=(w_{m+1,1},w_{m+1,2},..,w_{m_1,N})$ ，其中 $w_{m+1,i}={w_{mi}\over Z_m}e^{-\alpha_my_iG_m(x_i)}$ ， $Z_m=\sum_i^N{w_{mi}e^{-\alpha_my_iG_m(x_i)}}$
   5. 构建基本分类器的线性组合 $f(x)=\sum_m^M \alpha_mG_m(x)$
3. 得到最终的分类器 $G(x)=sign(f(x))$

阅读全文>>

什么是协同过滤

协同过滤(Collaborative Filtering, 简称CF)，wiki上的定义是：简单来说是利用某兴趣相投、拥有共同经验之群体的喜好来推荐使用者感兴趣的资讯，个人透过合作的机制给予资讯相当程度的回应（如评分）并记录下来以达到过滤的目的进而帮助别人筛选资讯，回应不一定局限于特别感兴趣的，特别不感兴趣资讯的纪录也相当重要。

以上定义太拗口，举个简单的例子：我现在多年不看日本anime的新番了，最近突然又想看几部新番，但又不知道这么多新番中看哪些比较好，于是我就找几个同样喜欢日本动漫的朋友来咨询。我第一个想咨询的朋友是和我口味最像的，我们都特别喜欢看《虫师》、《黑之契约者》、《寒蝉》这样的小众动画；我问的第二个朋友和我口味差不多，他特别喜欢看《钢炼》《无头骑士异闻录》这样的动画，我虽然喜欢，但不像他那么喜欢；由于身边喜欢日本动画的朋友不多，剩下第三个可以咨询的是一个宅女，平常经常看腐、宅、基的动漫，完全跟我不是一路人，于是问了下她推荐的片子，并将这些片子打上的黑名单的标签。然后我就开始看第一个朋友推荐的片子了，要是时间特别多又很无聊我可能会看第二个朋友推荐的，但打死我也不会看第三个朋友推荐的。这就是协同过滤的一个简化、小众版。

如何进行相似度度量

接着上面的例子，我可以通过我和其它朋友共同喜欢某个或某类动漫来确定我们的口味是否一样，那么如何以数学或者机器的形式来表示这个“口味一样”呢？通常，是通过“距离”来表示，例如：欧几里得距离、皮尔逊相关度、曼哈顿距离、Jaccard系数等等。

欧几里得距离

欧几里德距离（Euclidean Distance），最初用于计算欧几里得空间中两个点的距离，在二维空间中，就是我们熟悉的两点间的距离，x、y表示两点，维度为n：

$d(x,y)=\sqrt {(\sum_i^n (x_i-y_i)^2)}$

相似度：

$sim(x,y)={1\over {1+d(x,y)}}$

阅读全文>>

前几天与学弟聊到他最近的面试题中有一题需要计算两个字符串的最长公共子字符串。当时想到了KMP算法可能可以解决，但仔细想想可能是个比较复杂的任务。后来在网上看到有不少人说用trie树来解决。然后我就糊涂了，记忆中trie树貌似只能解决最长公共前缀的问题吧。于是复习一遍Trie树。

简介

Trie树百度百科解释如下：又称单词查找树，字典树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie树的直观结构如图所示：

图中红色的点代表此处有字符串在此结束，上图中共有7个字符串：abc、abcd、abd、b、bcd、efg、hij（百科中的图，空白边就算作j好了）。

Trie树的使用场景

• 字符串检索，词频统计，搜索引擎的热门查询。
• 字符串最长公共前缀。
• 字符串排序。
• 作为其他数据结构和算法的辅助结构，如后缀树，AC自动机等。

至于“计算两个字符串的最长公共子字符串”这样的需求无法采用trie树实现，就算能实现也需要大量的改变。

阅读全文>>

决策树

决策树是常用的分类算法之一，其对于探索式的知识发现往往有较好的表现。决策树原理十分简单，可处理大维度的数据，不用预先对模型的特征有所了解，这些特性使得决策树被广泛使用。决策树采用贪心算法，其建立过程同样需要训练数据。决策树算法有ID3、在ID3基础上发展起来的C4.5，以及C4.5的商业化版本C5.0，C5.0核心与C4.5相同，只是在执行效率和内存使用方面有所改进。

决策树的核心问题是决策树分支准则的确定，以及分裂点的确定。为了直观起见，推荐大家玩一个游戏：通过20个问题来猜出你心中所想的那个人。

初次接触这个游戏的你是否觉得十分神奇，在20个不到的问题里真的就能猜出你心中所想的那个人，不论是你的女朋友、父母或者动漫人物、歌手、演员甚至是政界人物。其实仔细想想，一个20层的二叉树最后的叶子节点有多少个？1024*1024个，而我们能想到的人绝对是超不出这个数量的。这个网站的具体算法就是采用的类似决策树的算法，通过一个个问题来减少候选的数据，直至找出你所想的那个人。

多玩几次你就会发现，一般第一个或前几个问题就会问你：你描述的对象是男（女）性吗？这意味着什么，意味着第一个问题就能将候选数据减少一半左右。因为你想的那个人，除了男人就是女人了。这就是前面所说的决策树分支准则的确定。若将这个问题放在最后几个问题中，毫无疑问是个吃力不讨好的事情。那么如何才能将这些众多属性（如：性别、高矮、胖瘦、头发长短、是否是歌手、是否有money等）按照其重要程度来排个顺序，这就是ID3和C4.5算法所做的事情了。

预备知识

信息熵是信息论中的基本概念。信息论是C.E.Shannon于1948年提出并由此发展起来的，主要用于解决信息传递过程中的问题，也称为统计通信理论。信息论认为：信息是用来消除随机不确定性的，信息量的大小可由所消除的不确定大小来计量。详细了解。

信息量的数学定义为：

$I(u_i)=-log_2P(u_i)$

其中 $P(u_i)$ 为信息 $u_i$ 发生的概率。信息熵是信息量的数学期望，是信源发出信息前的平均不确定性，也成为先验熵，信息熵的数学定义为：

$Ent(U)=-\sum_iP(u_i)log_2P(u_i)$

当已知信号 $U$ 的概率分布 $P(U)$ 且收到信号 $V=v_i$ 后，发出信号的概率分布变为 $P(U|v_j)$ ，于是信源的平均不确定性变为（也称为条件熵）：

$Ent(U|v_i)=-\sum_iP(u_i|v_i)log_2P(u_i|v_i)$

一般来说， $Ent(U|v_i) < Ent(U)$ ，于是定义信息增益为：

$Gains(U,V)=Ent(U)-Ent(U|V)$

阅读全文>>

Levenshtein距离，又称为编辑距离，或者成为字符串相似度，意思是一个字符串转换为另一个字符串所需要的最小编辑次数。编辑包含：插入、删除和替换三种操作。例如字符串：yurnom和yunum的编辑距离为2，因为需要插入一个r和将u替换为o两次操作。

Levenshtein算法由俄罗斯科学家Vladimir Levenshtein在1965年提出，该算法现在广泛用于DNA匹配、字符串纠错、实体共指等领域。

算法简介

将2个字符串转换为一个矩阵，为了简单起见，采用字符串heqi和hoi。转换后进行初始化，如下所示：

其中数字部分为初始化的值，现计算绿色格子A处的值，其算法为：

1. 若A所对应的两个字符相同，则左上角蓝色格子的值+0，否则+1，结果记为R1
2. 选取上方和左方紫色格子中较小的值，并+1，结果记为R2
3. 选取R1和R2中的较小值为绿色格子A处的值

经过计算可以得出A处的值为0，当A处计算完毕后，其右方和下方的值可以接着进行计算了，如此整个矩阵的值将可全部计算出来。最后矩阵右下方红色格子的值即为两个字符串的编辑距离。

至于为何左方和上方的值加1、左上角的值根据不同的情况加0或1的原因（也就是这么算的原理）比较简单，在此不再详述。

阅读全文>>

聚类算法

聚类，Cluster analysis，有时也被翻译为簇类，其核心任务是：将一组目标object划分为若干个簇，每个簇之间的object尽可能的相似，簇与簇之间的object尽可能的相异。聚类算法是机器学习（或者说是数据挖掘更合适）中重要的一部分，除了最为简单的K-Means聚类算法外，较常见的还有：层次法（CURE、CHAMELEON等）、网格算法（STING、WaveCluster等）等等。

较权威的聚类问题定义：所谓聚类问题，就是给定一个元素集合D，其中每个元素具有n个可观察属性，使用某种算法将D划分成k个子集，要求每个子集内部的元素之间相异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。

与分类不同，分类是示例式学习，要求分类前明确各个类别，并断言每个元素映射到一个类别，而聚类是观察式学习，在聚类前可以不知道类别甚至不给定类别数量，是无监督学习的一种。目前聚类广泛应用于统计学、生物学、数据库技术和市场营销等领域，相应的算法也非常的多。

K-Means

K-Means属于基于平方误差的迭代重分配聚类算法，其核心思想十分简单：

1. 随机选择K个中心点
2. 计算所有点到这K个中心点的距离，选择距离最近的中心点为其所在的簇
3. 简单的采用算术平均数（mean）来重新计算K个簇的中心
4. 重复步骤2和3,直至簇类不在发生变化或者达到最大迭代值
5. 输出结果

K-Means算法的结果好坏依赖于对初始聚类中心的选择，容易陷入局部最优解，对K值的选择没有准则可依循，对异常数据较为敏感，只能处理数值属性的数据，聚类结构可能不平衡。

这里有一个K-Means的演示，需要安装Java Applet。

阅读全文>>

分类算法

何为分类算法？简单来说，就是将具有某些特性的物体归类对应到一个已知的类别集合中的某个类别上。从数学角度来说，可以做如下定义：

已知集合： $C=\{y_1,y_2,..,y_n\}$ 和 $I=\{x_1,x_2,..,x_m,..\}$ ，确定映射规则 $y=f(x)$ ，使得任意 $x_i \in I$ 有且仅有一个 $y_j \in C$ 使得 $y_j=f(x_i)$ 成立。

其中，C为类别集合，I为待分类的物体，f则为分类器，分类算法的主要任务就是构造分类器f。

分类算法的构造通常需要一个已知类别的集合来进行训练，通常来说训练出来的分类算法不可能达到100%的准确率。分类器的质量往往与训练数据、验证数据、训练数据样本大小等因素相关。

举个例子，我们日常生活中看到一个陌生人，要做的第一件事情就是判断其性别，判断性别的过程就是一个分类的过程。根据以往的生活经验，通常经过头发长短、服饰和体型这三个要素就能判断出来一个人的性别。这里的“生活经验”就是一个训练好的关于性别判断的模型，其训练数据是日常生活中遇到的形形色色的人。突然有一天，一个娘炮走到了你面前，长发飘飘，穿着紧身的衣裤，可是体型却很man，于是你就疑惑了，根据以往的经验——也就是已经训练好的模型，无法判断这个人的性别。于是你学会了通过喉结来判断其性别，这样你的模型被训练的质量更高了。但不可否认的是，永远会出现一个让你无法判断性别的人。所以模型永远无法达到100%的准确，只会随着训练数据的不断增多而无限接近100%的准确。

贝叶斯公式

贝叶斯公式，或者叫做贝叶斯定理，是贝叶斯分类的基础。而贝叶斯分类是一类分类算法的统称，这一类算法的基础都是贝叶斯公式。目前研究较多的四种贝叶斯分类算法有：Naive Bayes、TAN、BAN和GBN。

理工科的学生在大学应该都学过概率论，其中最重要的几个公式中就有贝叶斯公式——用来描述两个条件概率之间的关系，比如P(A|B)和P(B|A)。如何在已知事件A和B分别发生的概率，和事件B发生时事件A发生的概率，来求得事件A发生时事件B发生的概率，这就是贝叶斯公式的作用。其表述如下：

$P(B|A)={P(A|B)\times P(B)\over P(A)}$

阅读全文>>