【信息科学与工程学】【数据科学】第五十五篇 大数据算法

1

MapReduce​

1.Map阶段:<k1, v1> -> list(<k2, v2>)
2.Shuffle & Sort: 按键k2分组，排序。
3.Reduce阶段:<k2, list(v2)> -> list(<k3, v3>)

分布式计算、函数式编程、容错处理

O(n)，取决于数据量和任务

海量、非结构化/结构化批数据

2

PageRank​

PR(pi​)=N1−d​+d∑pj​∈M(pi​)​L(pj​)PR(pj​)​
其中PR为页面权重，d为阻尼因子，L为出链数，N为总页面数。迭代计算直至收敛。

图论、线性代数、迭代计算

O(n*k)，n为页面数，k为迭代次数

图数据 (网页链接关系)

3

K-Means​

1. 目标函数（误差平方和）: (J = \sum{j=1}^{k} \sum{x \in C_j}

x - \mu_j

4

Apriori​

1. 支持度: Support(X)=Ncount(X)​
2. 频繁项集生成: 基于先验性质（频繁项集的所有子集也必须是频繁的）逐层搜索。
3. 关联规则生成: 置信度 Confidence(X→Y)=Support(X)Support(X∪Y)​

关联规则、集合论、搜索算法

O(2^n) 最坏情况，实际通过剪枝优化

事务型数据 (购物篮数据)

5

TF-IDF​

1. 词频: TF(t,d)=∑t′∈d​ft′,d​ft,d​​
2. 逆文档频率: (IDF(t, D) = \log \frac{N}{

{d \in D: t \in d}

} )
3. 综合权重: TF-IDF(t,d,D)=TF(t,d)×IDF(t,D)

信息检索、文本挖掘、向量空间模型

6

Bloom Filter​

1. 初始化一个长度为m、全为0的位数组。
2.添加元素: 使用k个哈希函数计算元素值，将对应位数组位置置1。
3.查询元素: 计算k个哈希值，若所有对应位均为1，则“可能存在”；任一为0，则“肯定不存在”。

概率数据结构、哈希函数、空间效率

O(k)，插入和查询均为常数时间

任意可哈希的数据对象

7

梯度提升决策树 (GBDT)​

1. 模型为加法模型: Fm​(x)=Fm−1​(x)+γm​hm​(x)
2. 每一轮拟合当前模型的负梯度（残差）: rim​=−[∂F(xi​)∂L(yi​,F(xi​))​]F(x)=Fm−1​(x)​
3. 通过决策树h_m(x)拟合r_{im}，并计算最优步长γ_m。

集成学习、决策树、梯度下降、损失函数

O(nmd*log n)，n样本数，m树数量，d特征数

数值/类别型特征，监督数据

8

Dijkstra算法​

1. 初始化距离: 起点dist[s]=0，其余dist[v]=∞。
2. 循环从优先队列中取出未处理且dist最小的顶点u。
3. 松弛操作: 对u的每个邻接点v，若dist[u] + w(u, v) < dist[v]，则更新dist[v]。

图论、贪心算法、优先队列

O(|E|+ |V|log |V|) (使用斐波那契堆)

带权有向/无向图数据

9

LSH (局部敏感哈希)​

核心思想: 将相似的数据点以高概率映射到同一个哈希桶中。
例如，对于余弦相似度，随机超平面哈希函数为: h(v)=sign(r⋅v)，其中r是随机向量。相似向量有更高概率得到相同符号。

近似最近邻搜索、概率论、度量空间

O(n*L)，n数据点，L哈希表数量

高维特征向量

10

流式处理 (如，滑动窗口平均)​

对于无限流数据，维护一个固定大小W的窗口。
窗口和更新: St​=St−1​+xt​−xt−W​
当前窗口平均值: xˉt​=WSt​​

数据流模型、滑动窗口、实时计算

O(1)，每次更新为常数时间

无界、有序的流数据

11

随机森林​

1. 自助采样(Bootstrap)得到k个训练集。
2. 为每个训练集构建决策树，节点分裂时从随机子集中选最优特征。
3. 分类任务：投票；回归任务：平均。 f^​=K1​∑k=1K​Tk​(x)

集成学习、Bagging、决策树、特征重要性

O(k * n * log(n) * m)，k树数量，n样本数，m特征数

数值/类别型特征，监督数据

12

支持向量机​

1. 优化目标（硬间隔）: (\min_{w,b} \frac{1}{2}

w

13

隐狄利克雷分布​

1. 文档生成过程：
- 从狄利克雷分布 Dir(α)采样得到文档的主题分布 θd​。
- 对文档中每个词：
a. 从 Multinomial(θd​)采样一个主题 zdn​。
b. 从主题 zdn​对应的词分布 ϕzdn​​(来自 Dir(β)) 中采样一个词 wdn​。
2. 通过吉布斯采样或变分推断求解参数。

主题模型、贝叶斯推断、概率图模型

O(nki)，n总词数，k主题数，i迭代次数

文本数据集合

14

协同过滤​

1.用户-物品评分矩阵​ Rm×n​。
2.基于用户的CF: 预测评分 (\hat{r}{ui} = \bar{r}u + \frac{\sum{v \in N(u)} sim(u, v) \cdot (r{vi} - \bar{r}v)}{\sum{v \in N(u)}

sim(u, v)

} )
3.基于物品的CF: 预测评分 (\hat{r}{ui} = \frac{\sum{j \in N(i)} sim(i, j) \cdot r{uj}}{\sum{j \in N(i)}

sim(i, j)

15

XGBoost​

1. 目标函数 = 损失函数 + 正则化项: Obj(t)=∑i=1n​L(yi​,y^​i(t−1)​+ft​(xi​))+Ω(ft​)
2. 二阶泰勒展开近似: Obj(t)≈∑i=1n​[gi​ft​(xi​)+21​hi​ft2​(xi​)]+Ω(ft​)
其中 gi​,hi​为一阶和二阶梯度。
3. 定义树结构，求解最优叶节点权重和分裂增益。

梯度提升、决策树、正则化、分布式计算

与GBDT类似，但工程优化极佳

数值/类别型特征，监督数据

16

Word2Vec​

1.Skip-gram目标: 最大化给定中心词 wc​下上下文词 wo​的平均对数概率: (\frac{1}{T} \sum{t=1}^{T} \sum{-c \le j \le c, j \ne 0} \log p(w_{t+j}

w_t) )
2. 使用softmax: (p(w_o

w_c) = \frac{\exp(u{o}^T v_c)}{\sum{w=1}^{W} \exp(u_{w}^T v_c)} )，常通过负采样优化。

词嵌入、分布式表示、神经网络、自然语言处理

17

Transformer (编码器)​

1.自注意力机制: Attention(Q,K,V)=softmax(dk​​QKT​)V，其中Q, K, V由输入线性变换得到。
2.多头注意力: 将多个自注意力头的结果拼接并线性变换。
3.前馈网络: FFN(x)=max(0,xW1​+b1​)W2​+b2​。
4. 残差连接与层归一化。

自注意力、位置编码、深度神经网络、并行计算

O(n² * d)，n序列长度，d模型维度

序列数据（文本、时序）

18

HyperLogLog​

1. 将元素通过哈希函数映射为二进制串。
2. 观察二进制串前导零的最大数量​ρ。
3. 分桶（m个）取平均以降低估计误差。
4. 基数估计值: E=αm​m2Z−1，其中 Z=∑j=1m​2−M[j]，M[j]为第j桶的ρ最大值。

基数估计、概率统计、哈希函数、流式统计

O(n)，n为数据流中唯一元素数量

海量数据流的独立元素计数

19

t-SNE​

1. 在高维空间计算数据点对之间的条件概率（相似度）: (p_{j|i} = \frac{\exp(-

x_i - x_j

20

C4.5 (决策树)​

1. 计算每个特征A的信息增益比: GainRatio(A)=SplitInfo(A)Gain(A)​
2. 信息增益: (Gain(A) = Entropy(S) - \sum_{v \in Values(A)} \frac{

S_v

}{

S

21

FP-Growth​

1. 扫描数据集，构建频繁项头表和FP树。
2. 从FP树的叶节点（项头表底部）开始，为每个频繁项构建条件模式基。
3. 对每个条件模式基，递归构建条件FP树，并挖掘频繁项集。

关联规则、频繁模式树、深度优先搜索

O(n * p)，n事务数，p频繁1-项集平均长度

事务型数据

22

KNN​

1. 给定测试样本，计算它与训练集中所有样本的距离（如欧氏距离）。
2. 选取距离最近的k个训练样本（邻居）。
3. 分类任务：统计k个邻居中最多数的类别；回归任务：取k个邻居目标值的平均。

惰性学习、距离度量、特征归一化

O(n * d)，查询时需计算与所有训练样本的距离

数值型特征向量，监督数据

23

AdaBoost​

1. 初始化样本权重 wi(1)​=1/N。
2. 对于每轮t：
a. 训练一个弱分类器 ht​，使其最小化加权误差 ϵt​。
b. 计算该分类器权重 αt​=21​ln(ϵt​1−ϵt​​)。
c. 更新样本权重: wi(t+1)​=wi(t)​exp(−αt​yi​ht​(xi​))/Zt​，Zt​为归一化因子。
3. 最终强分类器: H(x)=sign(∑t=1T​αt​ht​(x))

集成学习、Boosting、加法模型

O(T * f(n))，T迭代次数，f(n)是弱分类器训练复杂度

数值/类别型特征，监督数据

24

EM算法​

1.E步（期望）: 基于当前参数 θ(t)计算隐变量 Z的后验概率 Q(z∥x,θ(t))。
2.M步（最大化）: 更新参数 θ(t+1)=argmaxθ​∑z​Q(z∥x,θ(t))logP(x,z∥θ)。
3. 迭代直至收敛。

最大似然估计、隐变量模型、高斯混合模型

迭代算法，每次迭代复杂度取决于具体模型

含隐变量的不完全数据

25

Bellman-Ford​

1. 初始化距离数组dist[]，起点为0，其余为∞。
2. 对每条边松弛`

V

-1次: 如果dist[u] + w(u, v) < dist[v]，则更新dist[v] = dist[u] + w(u, v)`。
3. 再检查一次所有边，若还能松弛则说明存在负权环。

图论、动态规划、单源最短路径

26

最小哈希​

1. 定义特征矩阵的行的一个随机排列。
2. 对于每个集合（列），其最小哈希值为：在该排列下，第一个出现“1”的行索引。
3. 使用多个随机排列生成签名矩阵。
4. 两个集合的Jaccard相似度 ≈ 它们的签名向量中对应位置值相等的比例。

集合相似度估计、Jaccard相似度、哈希

O(n * m)，n特征数，m集合数，但通过哈希函数模拟排列可优化

集合数据（如文档的词袋表示）

27

CURE聚类​

1. 对数据集进行随机采样。
2. 对采样点进行预聚类（如层次聚类）。
3. 对每个簇，选取固定数量的分散的点作为代表点，并将其向簇中心收缩以消除噪声影响。
4. 对所有代表点进行聚类，并将剩余点分配到最近的簇。

层次聚类、采样、对噪声和形状鲁棒

O(n² log n) 最坏，采样后大幅降低

数值型数据，尤其对非球形簇有效

28

PrefixSpan​

1. 扫描数据库，找出所有长度为1的频繁序列。
2. 为每个频繁项α，构建其对应的投影数据库。
3. 在投影数据库上递归地挖掘以α为前缀的更长频繁序列。

序列模式挖掘、投影数据库、深度优先搜索

O(n * m)，n序列数，m频繁模式长度

序列数据（如用户行为序列）

29

SVD (奇异值分解)​

将矩阵 Am×n​分解为: A=UΣVT
其中 Um×m​，Σm×n​(对角阵)，Vn×n​是酉矩阵。
取前k个最大奇异值及其对应向量，得到降维或近似矩阵: Ak​=Uk​Σk​VkT​

线性代数、矩阵分解、降维、推荐系统

O(min(m²n, mn²))，完整SVD；截断SVD可优化

任何实数矩阵（如评分矩阵、词-文档矩阵）

30

Count-Min Sketch​

1. 初始化d个长度为w的计数器数组，对应d个哈希函数。
2.更新（频次+1）: 对元素x，计算d个哈希值 hj​(x)，对每个数组j，将位置 hj​(x)的计数器加1。
3.查询频次: 返回 f^​(x)=min1≤j≤d​count[j][hj​(x)]

流数据、频率估计、概率数据结构

O(d)，更新和查询均为常数时间

数据流中的元素（如IP、搜索词）