机器学习

做机器学习的实验做得我生无可恋，还是先补一下机器学习的几个算法的基本原理再说吧。

1. 统计学习概述

1.1. 统计学习三要素

• 模型：确定学习模型的集合。模型在未进行训练前，其可能的参数是多个甚至无穷的，故可能的模型也是多个甚至无穷的，这些模型构成的集合就是假设空间。

  

• 策略：确定模型选择的准则。即从假设空间中挑选出参数最优的模型的准则。模型的分类或预测结果与实际情况的误差（损失函数）越小，模型就越好。那么策略就是误差最小。

  

• 算法：实现求解最优模型的算法。即从假设空间中挑选模型的方法（等同于求解最佳的模型参数）。机器学习的参数求解通常都会转化为最优化问题，故学习算法通常是最优化算法，例如最速梯度下降法、牛顿法以及拟牛顿法等。

以上是针对监督学习的三要素，下面是针对无监督学习的三要素：

1.2. 监督学习

监督学习：从标注数据中学习预测模型的机器学习问题，其本质是学习输入到输出的映射的统计规律。

输入空间：输入的所有可能取值的集合。

实例：每一个具体的输入，通常由特征向量表示。

特征空间：所有特征向量存在的空间。

输出空间：输出的所有可能取值的集合。

根据变量类型的不同，可分为回归问题、分类问题和标注问题。

回归问题：输入变量与输出变量均为连续变量的预测问题。

分类问题：输出变量为有限个离散变量的预测问题。

标注问题：输入变量与输出变量均为变量序列的预测问题。

1.3. 无监督学习

无监督学习：从无标注数据中学习预测模型的机器学习问题，其本质是学习数据中的统计规律或潜在结构。

1.4 模型评估与选择

训练误差：

测试误差：

误差率与准确率：

多项式拟合案例：

过拟合：学习时选择的模型所包含的参数过多，以至于出现这一模型对已知数据预测得很好，但对未知数据预测得很差的现象。

欠拟合：模型拟合程度不高，数据距离拟合曲线较远，或指模型没有很好地捕捉到数据特征，不能够很好地拟合数据。

为了避免过拟合的问题出现，需要选择合适的模型。常用的模型选择方法：正则化和交叉验证。

1.5 正则化和交叉验证

1.5.1 正则化

正则化：实现结构风险最小化策略。

奥卡姆剃刀原理：在模型选择时，选择所有可能模型中，能很好解释已知数据并且十分简单的模型。

1.5.2 交叉验证

在数据不足的情况下：

• 简单交叉验证：随即将数据分为两部分，即训练集和测试集。
• S折交叉认证：随机将数据分为S个互不相交、大小相同的子集，其中以S-1个子集作为训练集，余下的子集作为测试集。
• 留一交叉验证：S折交叉验证的特殊情形，S=N，N为数据集的样本容量。(在数据极少的情况下使用)

1.6 泛化能力

1.7 生成模型与判别模型

1.7.1 生成模型

1.7.2 判别模型

1.7.3 两者区别

1.8 监督学习应用

1.8.1 分类问题

方法：感知机、K近邻法、朴素贝叶斯、决策树、Logistic回归。

应用：银行业务、网络安全、图像处理、手写识别、互联网搜索。

1.8.2 标注问题

方法：隐马尔可夫模型、条件随机场。

应用：信息抽取、自然语言处理。

1.8.3 回归问题

类型：

• 按输入变量个数：一元回归、多元回归
• 按输入和输出变量之间的关系：线性回归、非线性回归

损失函数：平方损失

应用：商务领域

2. 感知机

2.1 感知机模型

在几何中，如果特征空间是n维的，则超平面是n-1维的子空间。比如特征空间是2维的，那么超平面就是一条直线，超平面用来分隔正类和负类。

2.2 梯度下降法

例子：

梯度下降法的原理：

2.3 感知机的原始形式

感知机采用监督学习中的二分类问题。原始形式用随机梯度下降法来更新w和b。

原始形式的算法：

例题分析：

2.4 感知机的对偶形式

对偶形式的算法：

例题分析：

2.5 算法的收敛性

3. K近邻

3.1 K近邻相关概念

K近邻算法：

误差率：

3.2 K近邻三要素

3.2.1 K近邻模型

3.2.2 距离度量

3.2.3 K值的选择

近似误差：可以理解为对现有训练集的训练误差。

估计误差：可以理解为对测试集的测试误差。

3.2.4 分类决策规则

3.3 构造KD树

例子：

3.4 搜索KD树

最近邻搜索：

• 寻找“当前最近点”：寻找最近邻的子结点作为目标点的“当前最近点”
• 回溯：以目标点和“当前最近点”的距离沿树根部进行回溯和迭代

最近邻搜索算法：

例子：

4. 朴素贝叶斯法

4.1 贝叶斯定理

条件概率公式：

$$P(X=x|Y=y_i)=\frac {P(X=x,Y=y_i)}{P(Y=y_i)}$$

全概率公式：

$$P(X=x)=\sum_{i=1}^nP(Y=y_i)P(X=x|Y=y_i)$$

贝叶斯公式：

$$P(Y=y_i|X=x)=\frac {P(X=x,Y=y_i)}{P(X=x)}$$

根据条件概率公式，得到最终的贝叶斯公式：

$$P(Y=y_i|X=x)=\frac{P(Y=y_i)P(X=x|Y=y_i)}{\sum_{i=1}^nP(Y=y_i)P(X=x|Y=y_i)}$$

4.2 何为朴素

参数个数：

“朴素”即为条件独立性假设，即特征之间相互独立。

4.3 后验概率最大化

将期望风险最小化转化为后验概率最大化的问题。

4.4 极大似然估计

极大似然估计原理：

极大似然估计实现：

4.5 算法

4.6 贝叶斯估计

5. 决策树

分类决策树模型是一种描述对实例进行分类的树形结构。

决策树是通过一系列规则对数据进行分类的过程。

If-Then规则：

构建决策树：

1. 构建根节点
2. 选择最优特征，以此分割训练数据集
3. 若子集被基本正确分类，构建叶结点；否则，继续选择新的最优特征
4. 重复2、3步，直到所有训练数据子集被正确分类

5.1 条件概率分布

当单元c的条件概率满足时，则认为该单元属于正类。

5.2 决策树学习

5.3 特征选择

根据选择不同的特征作为根结点所得到的决策树不同。那么，如何进行特征选择呢？信息增益。

例子：

计算年龄特征的经验条件熵：

计算工作特征的经验条件熵：

计算有房子特征的经验条件熵：

计算信贷情况特征的经验条件熵：

信息增益：

哪个带来的信息增益最大选哪个特征作为根结点。

信息增益比：

哪个信息增益比最大选哪个特征作为根结点。

信息增益倾向于某个取值较多的特征，信息增益比倾向于某个取值较少的特征。

5.4 决策树的生成

5.4.1 ID3算法

例子：

5.4.2 C4.5算法

5.5 剪枝

5.5.1 预剪枝

预剪枝的几个方法：

1. 限定决策树的深度
2. 设置一个阈值
3. 设置某个指标，比较结点划分前后的泛化能力

例子：

深度为4，假设限定决策树的深度为2：

设定阈值为0.4：

设置阈值过大，导致欠拟合现象。

设置某个指标，比较结点划分前后的泛化能力：

此时的误差率为。

经过计算，脐部特征的信息增益最大，将它作为根结点。判断测试集的泛化能力，误差率为，比之前的误差率小，所以应该继续往下递归。

在脐部的特征值为凹陷的训练集中，色泽的信息增益最大，将它作为子树。

此时算出误差率为，比大，所以泛化能力下降，应该将它预剪枝。

在脐部的特征值为稍凹的训练集中，根蒂的信息增益最大，将它作为子树。

此时算出误差率为，与之前误差率相同。根据奥卡姆剃刀原理，在相同效果下，越简单越好，所以也将它预剪枝。

在脐部的特征值为平坦的训练集中，全是坏瓜，没有必要再次做划分。

5.5.2 后剪枝

后剪枝的几个方法：

1. 降低错误剪枝(REP)
2. 悲观错误剪枝(PEP)
3. 最小误差剪枝(MEP)
4. 基于错误的剪枝(EBP)
5. 代价-复杂度剪枝(CCP)

5.5.2.1 降低错误剪枝(REP)

如果不剪枝，误判个数为2：

剪枝后误判个数为1个，所以应该剪枝：

继续看能不能从3层变2层，色泽中的三个特征值有两个判断为好瓜，所以直接将稍蜷缩的判断为好瓜。

在剪枝前，误判个数为1个：

在剪枝后，误判个数为1个：

根据奥卡姆剃刀原理，选择剪枝。

继续看能不能从2层变1层，分别判断色泽特征和根蒂特征。最后可以得出是可以的：

5.5.2.2 悲观错误剪枝(PEP)

原理：根据剪枝前后的错误率来决定是否剪枝。和REP不同之处在于PEP只需要训练集即可，不需要验证集，并且PEP是自上而下剪枝的。

例子：

悲观错误剪枝的特点：

• 不需要分离剪枝数据集，有利于实例较少的问题
• 误差使用了连续修正值，使得适用性更强
• 由于自上而下的剪枝策略，PEP效率更高
• 可能会修剪不应剪掉的枝条

5.5.2.3 最小误差剪枝(MEP)

原理：根据剪枝前后的最小分类错误概率来决定是否剪枝。自下而上剪枝，只需要训练集即可。

在实际操作中，m是选出来，而不是指定的。

例子：

5.5.2.4 基于错误剪枝(EBP)

原理：根据剪枝前后的误判个数来决定是否剪枝。自下而上剪枝，只需要训练集即可。

例子：

5.5.2.5 代价-复杂度剪枝(CCP)

原理：根据剪枝前后的损失函数来决定是否剪枝。

5.6 CART算法

CART算法是二叉决策树。

5.6.1 树的生成

5.6.1.1 分类树

将甜度特征作为分类：

将硬度特征作为分类：

0.48 > 0.17，甜度特征更有利于桃子的分类，因为它的基尼指数更小，分得更彻底。

CART分类决策树算法：

例子：

对比这四个特征的基尼指数，发现第三个特征的基尼指数最小，所以用它作为根结点来进行划分。再来看其它三个特征，重复上述步骤。

5.6.1.2 回归树

回归树算法：

5.6.2 树的剪枝

6. 逻辑回归

7. 最大熵模型

7.1 最大熵原理

7.1.1 离散分布

7.1.2 连续分布

在连续变量的情况下，最大熵是正态分布。证明如下：

7.2 最大熵模型

经验分布相当于上帝视角的估计值。

7.3 寻找最大条件熵

拉格朗日乘子法：

原始问题：

对偶问题：

原始问题和对偶问题的最优解：

7.4 最大熵模型的学习

原始问题和对偶问题的最优解相同吗？

证明熵函数H(P)是严格凹函数(上凸函数)：

利用对偶问题解决原始问题：

例子：

7.5 极大似然估计

7.6 优化算法

7.6.1 最速梯度下降法

7.6.2 牛顿法

7.6.2.1 求零点

7.6.2.1 求极小值

例子：

推广到求多元的情况下：

7.6.3 拟牛顿法

7.6.3.1 条件

7.6.3.2 一维搜索

7.6.3.3 DFP算法

DFP应用于最大熵模型：

7.6.3.4 BFGS算法

BFGS应用于最大熵模型：

7.6.3.5 Broyden算法

7.6.4 迭代尺度法

8. 支持向量机

8.1 线性可分支持向量机

8.1.1 原始算法

8.1.2 对偶算法

8.2 线性不可分支持向量机

8.2.1 原始算法

8.2.2 对偶算法

8.2.3 合页损失

8.3 非线性支持向量机

8.3.1 核函数

8.3.2 定义在欧氏空间的正定核函数

8.3.3 定义在离散数据集合的正定核函数

8.3.4 非支持向量机的算法

8.3.4.1 坐标下降法

8.3.4.2 SMO(序列最小最优)算法

9. 聚类方法

9.1 相似度或距离

聚类的核心概念是相似度（similarity) 或距离（distance)，有多种相似度或距离定义。因为相似度直接影响聚类的结果，所以其选择是聚类的根本问题。

9.1.1 闵可夫斯基距离

闵可夫斯基距离：距离越大相似度越小，距离越小相似度越大。

给定样本集合X，X是m维实数向量空间中点的集合，其中

$$x_i,x_j\in X,x_i=(x_{1i},x_{2i},...,x_{mi})^\mathrm T,x_j=(x_{1j},x_{2j},...,x_{mj})^\mathrm T$$

样本与样本的闵可夫斯基距离定义为：

$$d_{ij}=(\sum_{k=1}^m|x_{ki}-x_{kj}|^p)^\frac1p,其中p\ge1$$

• 当p=2时称为欧氏距离

  $$d_{ij}=(\sum_{k=1}^m|x_{ki}-x_{kj}|^2)^\frac12$$

• 当p=1时称为曼哈顿距离

  $$d_{ij}=\sum_{k=1}^m|x_{ki}-x_{kj}|$$

• 当p趋近于无穷时称为切比雪夫距离

  $$d_{ij}=\max_k|x_{ki}-x_{kj}|$$

9.1.2 马哈拉诺比斯距离

马哈拉诺比斯距离：距离越大相似度越小，距离越小相似度越大。

给定一个样本集合X，$X=[x{ij}]{m×n}x_ix_j$之间的马哈拉诺比斯距离定义为：

$$d_{ij}=[(x_i-x_j)^\mathrm TS^{-1}(x_i-x_j)]^\frac12$$

其中$xi=(x{1i},x{2i},…,x{mi})^\mathrm T,xj=(x{1j},x{2j},…,x{mj})^\mathrm T$。

协方差的计算公式被定义为：

$$\sigma(x,y)=\frac1{n-1}\sum_{i=1}^n(x_i-\overline x)(y_i-\overline y)$$

其中n表示样本数量，分别表示两个随机变量所对应的观测样本均值。

样本的协方差矩阵定义为：

$$\begin{pmatrix} \sigma(x_1,x_1)&\cdots&\sigma(x_1,x_d)\\ \vdots&\ddots&\vdots\\ \sigma(x_d,x_1)&\cdots&\sigma(x_d,x_d)\\ \end{pmatrix}\in \R^{d×d}$$

如果协方差矩阵是单位矩阵，马哈拉诺比斯距离就简化为欧氏距离。

9.1.3 相关系数

相关系数的绝对值越接近于1，表示样本越相似；越接近于0，表示样本越不相似。

样本与样本之间的相关系数定义为：

$$r_{ij}=\frac{\sum_{k=1}^m(x_{ki}-\overline x_i)(x_{kj}-\overline x_j)}{[\sum_{k=1}^m(x_{ki}-\overline x_i)^2\sum_{k=1}^m(x_{kj}-\overline x_j)^2]^\frac12}$$

其中$\overline xi=\frac1 m\sum{k=1}^mx{ki},\overline x_j=\frac 1m\sum{k=1}^mx_{kj}$。

6.1.4 夹角余弦

夹角余弦越接近于1，表示样本越相似；越接近于0，表示样本越不相似。

样本与样本之间的夹角余弦定义为：

$$s_{ij}=\frac{\sum_{k=1}^mx_{ki}x_{kj}}{[\sum_{k=1}^mx_{ki}^2\sum_{k=1}^mx_{kj}^2]^\frac12}$$

9.2 类或簇

通过聚类得到的类或簇，本质是样本的子集。

硬聚类：一个样本只能属于一个类，或类的交集为空集。

软聚类：一个样本可以属于多个类，或类的交集不为空集。

用G表示类或簇(cluster)，用$xi, x_jn_Gd{ij}x_ix_j$之间的距离。

定义1：设T为给定的正数，若集合G中任意两个样本$xi,x_jd{ij}\le T$，则称G为一个类或簇。

定义2：设T为给定的正数，若对集合G的任意一个样本$xix_jd{ij}\le T$，则称G为一个类或簇。

定义3：设T为给定的正数，若对集合G中任意一个样本$xix_j\frac1{n_G-1}\sum{xj\in G}d{ij}\le Tn_G$为G中样本的个数，则称G为一个类或簇。

定义4：设T和V为给定的两个正数，如果集合G中任意两个样本$xi,x_jd{ij}\frac1{nG(n_G-1)}\sum{xi\in G}\sum{xj\in G}d{ij}\le Td_{ij}\le V$，则称G为一个类或簇。

9.3 层次聚类

层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。因为每个样本只属于一个类，所以层次聚类属于硬聚类。

层次聚类又有聚合或自下而上聚类、分裂或自上而下聚类两种方法。

• 聚合聚类开始将每个样本各自分到一个类，之后将相距最近的两类合并，建立一个新的类，重复此操作直到满足停止条件，得到层次化的类别。
• 分裂聚类开始将所有样本分到一个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件，得到层次化的类别。

9.3.1 聚合聚类

聚合聚类需要预先确定三个要素：距离或相似度、合并规则、停止条件。

聚合聚类算法：

例子：给定5个样本的集合，样本之间的欧氏距离由如下矩阵D表示

$$D=[d_{ij}]_{5×5}= \begin{pmatrix} 0&7&2&9&3\\ 7&0&5&4&6\\ 2&5&0&8&1\\ 9&4&8&0&5\\ 3&6&1&5&0 \end{pmatrix}$$

其中表示第i个样本与第j个样本之间的欧氏距离。显然D为对称矩阵。应用聚合层次聚类法对这5个样本进行聚类。

解：

首先用5个样本构建5个类，。这样，样本之间的距离也就变成类之间的距离，所以5个类之间的距离矩阵亦为D。

由矩阵D可以看出，$d{35}=d{53}=1G_3G_5G_6={x_3,x_5}$。

计算与之间的最短距离，为

$$d_{61}=\min(d_{31},d_{51})=2\\ d_{62}=\min(d_{32},d_{52})=5\\ d_{64}=\min(d_{34},d_{54})=5$$

三类之间的距离从矩阵中可以看出：

$$d_{12}=7\\ d_{14}=9\\ d_{24}=4$$

显然，最小，所以将和合并成一个新类，记作。

计算与之间的最短距离，为

$$d_{72}=\min(d_{12},d_{32},d_{52})=5\\ d_{74}=\min(d_{14},d_{34},d_{54})=5$$

$G2,G_4d{24}=4d_{24}=4G_2G_4G_8={x_2,x_4}$。

最后将合并成一个新类，记作。至此，所有样本聚成一类，聚类终止。

9.4 k均值聚类

k均值聚类是基于样本集合划分的聚类算法。每个样本只能属于一个类，所以k均值聚类是硬聚类。

k均值聚类将样本集合划分为k个子集，构成k个类，将n个样本分到k个类中，每个样本到其所属类的中心的距离最小。

模型：用C表示划分，一个划分对应着一个聚类结果。划分C是多对一函数，划分或者聚类可以用函数表示，其中样本用一个整数表示，类用一个整数表示。

策略：通过损失函数的最小化选取最优的划分或函数C*。

首先采用欧氏距离平方作为样本之间的距离

$$d(x_i,x_j)=\sum_{k=1}^m(x_{ki}-x_{kj})^2=||x_i-x_j||^2$$

然后，定义样本与其所属类的中心之间的距离的总和为损失函数，即

$$W(C)=\sum_{l=1}^k\sum_{C(i)=l}||x_i-\overline x_l||^2$$

其中$\overline xl=(\overline x{1l},\overline x{2l},…,\overline x{ml})^\mathrm Tnl=\sum{i=1}^nI(C(i)=l)I(C(i)=l)$是指示函数，取值1或0。

函数W(C)也称为能量，表示相同类中样本相似的程度。

k均值聚类就是求解最优化问题：

$$C^*=\arg\min_CW(C)=\arg\min_C\sum_{l=1}^k\sum_{C(i)=l}||x_i-\overline x_l||^2$$

相似的样本被聚到同类时，损失函数值最小，这个目标函数的最优化能达到聚类的目的。

事实上，k均值聚类的最优解求解问题是NP困难问题。现实中采用迭代的方法求解。

算法：k均值聚类的算法是一个迭代的过程，每次迭代包括两个步骤。

1. 首先选择k个类的中心，将样本逐个指派到与其最近的中心的类中，得到一个聚类结果
2. 然后更新每个类的样本的均值，作为类的新的中心
3. 重复以上步骤，直到收敛为止。

k均值聚类算法：

例子：

给定含有5个样本的集合

$$X= \begin{pmatrix} 0&0&1&5&5\\ 2&0&0&0&2 \end{pmatrix}$$

试用k均值聚类算法将样本聚到2个类中。

解：

选择两个样本点作为类的中心。假设选择。

以为类的中心，计算与的欧氏距离平方。

对，

$$d(x_3,m_1^{(0)})=(1-0)^2+(0-2)^2=5\\ d(x_3,m_2^{(0)})=(1-0)^2+(0-0)^2=1$$

将分到类。

对，

$$d(x_4,m_1^{(0)})=(5-0)^2+(0-2)^2=29\\ d(x_4,m_2^{(0)})=(5-0)^2+(0-0)^2=25$$

将分到类。

对，

$$d(x_5,m_1^{(0)})=(5-0)^2+(2-2)^2=25\\ d(x_5,m_2^{(0)})=(5-0)^2+(2-0)^2=29$$

将分到类。

得到新的类，计算类的中心

$$m_1^{(1)}=(\frac {0+5}{2},\frac{2+2}2)^\mathrm T=(2.5,2)^\mathrm T\\ m_2^{(1)}=(\frac {0+1+5}{3},\frac{0}3)^\mathrm T=(2,0)^\mathrm T$$

对，将分到类。

对，将分到类。

对，将分到类。

对，将分到类。

对，将分到类。

得到新的类。

由于得到的新的类没有改变，聚类停止。得到聚类结果：$G_1^={x_1,x_5},G_2^={x_2,x_3,x_4}$。

10. PageRank算法

10.1 PageRank算法的基本思想

PageRank算法的基本思想是在有向图上定义一个随机游走模型，即一阶马尔可夫链，描述随机游走者沿着有向图随机访问各个结点的行为。在一定条件下，极限情况访问每个结点的概率收敛到平稳分布，此时各个结点的平稳概率值就是其PageRank值，表示结点的重要度。

PageRank是递归定义的，PageRank的计算可以通过迭代算法进行。

PageRank的基本定义是理想化的，在这种情况下，PageRank存在，而且可以通过不断迭代求得PageRank值。一般的有向图未必满足强连通且非周期性的条件，所以PageRank 的基本定义不适用。

假设有向图的转移矩阵为

这时M不是一个随机矩阵，因为随机矩阵要求每一列的元素之和是1，这里第3列的和是0，不是1。如果仍然计算在各个时刻的各个结点的概率分布，随着迭代次数增加，访问各个结点的概率均变为0。

PageRank一般定义的想法是在基本定义的基础上导入平滑项。

10.2 迭代算法

例子：

图中所示的有向图，取d = 0.8，求图的PageRank。

解：

根据有向图可得转移矩阵（列表示出度，行表示入度）：

$$M= \begin{pmatrix} 0&\frac12&0&0\\ \frac13&0&0&\frac12\\ \frac13&0&1&\frac12\\ \frac13&\frac12&0&0 \end{pmatrix}$$

则

$$dM=\frac45×M= \begin{pmatrix} 0&\frac12&0&0\\ \frac13&0&0&\frac12\\ \frac13&0&1&\frac12\\ \frac13&\frac12&0&0 \end{pmatrix}= \begin{pmatrix} 0&\frac25&0&0\\ \frac4{15}&0&0&\frac25\\ \frac4{15}&0&\frac45&\frac25\\ \frac4{15}&\frac25&0&0 \end{pmatrix}\\ \frac {1-d}{n}1= \begin{pmatrix} \frac1{20}\\ \frac1{20}\\ \frac1{20}\\ \frac1{20} \end{pmatrix}$$

所以迭代公式为

$$R_{t+1}=\begin{pmatrix} 0&\frac25&0&0\\ \frac4{15}&0&0&\frac25\\ \frac4{15}&0&\frac45&\frac25\\ \frac4{15}&\frac25&0&0 \end{pmatrix}R_t+\begin{pmatrix} \frac1{20}\\ \frac1{20}\\ \frac1{20}\\ \frac1{20} \end{pmatrix}$$

令初始向量为

$$R_0=\begin{pmatrix} \frac14\\ \frac14\\ \frac14\\ \frac14 \end{pmatrix}$$

进行迭代

$$R_{1}=\begin{pmatrix} 0&\frac25&0&0\\ \frac4{15}&0&0&\frac25\\ \frac4{15}&0&\frac45&\frac25\\ \frac4{15}&\frac25&0&0 \end{pmatrix}\begin{pmatrix} \frac14\\ \frac14\\ \frac14\\ \frac14 \end{pmatrix}+\begin{pmatrix} \frac1{20}\\ \frac1{20}\\ \frac1{20}\\ \frac1{20} \end{pmatrix}=\begin{pmatrix} \frac9{60}\\ \frac{13}{60}\\ \frac{25}{60}\\ \frac{13}{60} \end{pmatrix}\\ R_{2}=\begin{pmatrix} 0&\frac25&0&0\\ \frac4{15}&0&0&\frac25\\ \frac4{15}&0&\frac45&\frac25\\ \frac4{15}&\frac25&0&0 \end{pmatrix}\begin{pmatrix} \frac9{60}\\ \frac{13}{60}\\ \frac{25}{60}\\ \frac{13}{60} \end{pmatrix}+\begin{pmatrix} \frac1{20}\\ \frac1{20}\\ \frac1{20}\\ \frac1{20} \end{pmatrix}=\begin{pmatrix} \frac{41}{300}\\ \frac{53}{300}\\ \frac{153}{300}\\ \frac{53}{300} \end{pmatrix}\\ \vdots$$

最后得到

计算结果表明，结点C的PageRank值超过一半，其他结点也有相应的PageRank值。

10.3 代数算法

代数算法通过一般转移矩阵的逆矩阵计算求有向图的一般PageRank。

按照一般PageRank的定义式

$$R=dMR+\frac{1-d}n1$$

于是

$$(I-dM)R=\frac{1-d}m1$$

这里的I是单位矩阵。当时，线性方程组的解存在且唯一，即

$$R=(I-dM)^{-1}\frac{1-d}n1$$

这样，可以通过求逆矩阵得到有向图的一般PageRank。

$$I-dM=\begin{pmatrix}1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\end{pmatrix}-\begin{pmatrix} 0&\frac25&0&0\\ \frac4{15}&0&0&\frac25\\ \frac4{15}&0&\frac45&\frac25\\ \frac4{15}&\frac25&0&0 \end{pmatrix}=\begin{pmatrix}1&-\frac25&0&0\\ -\frac4{15}&1&0&-\frac25\\ -\frac4{15}&0&\frac15&0\\ -\frac4{15}&-\frac25&0&1\end{pmatrix}$$

求可用矩阵求逆方法初等行变换解得。进而与进行内积运算，得到PageRank值。