奇异值分解

奇异值分解，singular value decomposition（SVD）是线性代数中一种重要的矩阵分解。

记得大学时学习线性代数中的特征值和特征向量时，我就一直思考这个玩意算出来到底有啥用，难不成就是一群热（xian）爱（de）专（dan）研（teng）的人弄出来的数学小把戏？然后随着时间的推移，这些纯理论的东西就基本忘光了。大学的知识往往都这样的，和实际不接轨，学的时候不知道有啥用，等用的时候就忘的差不多了。

现在，在我学习线性代数后的第8年，我终于知道特征值这个玩意有啥用了。首先，先回忆下什么是特征值和特征向量吧。

特征值

对于一个方阵，其特征值和特征向量满足：

$A\nu=\lambda\nu$

求出所有的特征值和特征向量后，就得出了方阵A的特征值分解：

$A=Q\Sigma Q^{-1}$

其中 $Q$ 是特征向量按照与特征值的对应顺序组合而成 $(\nu_1,\nu_2,..)$ ， $\Sigma$ 是由特征值组成的一个对角矩阵。那么对于方阵A的特征值分解的意义又何在呢？先看下面这个例子，对于矩阵A（为了简单起见，设为对角矩阵）：

$A=\left(\begin{array}{ccc}100 & 0 & 0 \\0 & 10 & 0 \\0 & 0 & 1 \\\end{array}\right)$

阅读全文>>

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)}}$

阅读全文>>

决策树

决策树是常用的分类算法之一，其对于探索式的知识发现往往有较好的表现。决策树原理十分简单，可处理大维度的数据，不用预先对模型的特征有所了解，这些特性使得决策树被广泛使用。决策树采用贪心算法，其建立过程同样需要训练数据。决策树算法有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)$

阅读全文>>

本文不涉及线性回归具体算法和原理性的东西，纯新手向、介绍性的文章。

线性回归

线性回归，对于初学者而言（比方说我）比较难理解，其实换个叫法可能就能立马知道线性回归是做什么的了：线性拟合。所谓拟合，就简单多了，如下图所示：

线性拟合，顾名思义拟合出来的预测函数是一条直线，数学表达如下：

$h(x)=a_0+a_1x_1+a_2x_2+..+a_nx_n+J(\theta)$

其中 $h(x)$ 为预测函数， $a_i(i=1,2,..,n)$ 为估计参数，模型训练的目的就是计算出这些参数的值。

而线性回归分析的整个过程可以简单描述为如下三个步骤：

1. 寻找合适的预测函数，即上文中的 $h(x)$ ，用来预测输入数据的判断结果。这个过程时非常关键的，需要对数据有一定的了解或分析，知道或者猜测预测函数的“大概”形式，比如是线性函数还是非线性函数，若是非线性的则无法用线性回归来得出高质量的结果。
2. 构造一个Loss函数（损失函数），该函数表示预测的输出（h）与训练数据标签之间的偏差，可以是二者之间的差（h-y）或者是其他的形式（如平方差开方）。综合考虑所有训练数据的“损失”，将Loss求和或者求平均，记为 $J(\theta)$ 函数，表示所有训练数据预测值与实际类别的偏差。
3. 显然， $J(\theta)$ 函数的值越小表示预测函数越准确（即h函数越准确），所以这一步需要做的是找到 $J(\theta)$ 函数的最小值。找函数的最小值有不同的方法，Spark中采用的是梯度下降法（stochastic gradient descent, SGD)。

阅读全文>>

聚类算法

聚类，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)}$

阅读全文>>