《数据挖掘》课程简易复习提纲，主要根据PPT整理。时间仓促，不排除存在部分内容爆炸。

Intro

Data Mining: process of semi-automaticlly analyzing large databases to find patterns that are:

Valid: hold on new data with certainty
Novel: non-obvious to the system
Useful: should be possible to act on the item
Understandable: humans should be able to interpret the pattern

Data Exploration

数据具有属性(attribute/feature)，属性可以分为Norminal、Binary、Ordinal或者Numeric的，也可以分为连续的或离散的。

度量数据

度量中心

度量中心的方式包括Mean平均数，Medium中位数和众数Mode。根据这三种数的位置关系可以分为symmetric和asymmetric(Positively skew和Negatively skew)两种

度量离散程度

Quantile，常用的有四分位数，把Q3-Q1定义为IQR(Interquartile range)。
在作业中还提到了absolute deviation，表示到中心点（median、mean、mode）的度量，等于
$$
\frac{1}{n} \sum^{n}_{i = 1}{|x_i - m(X)|}
$$

数据可视化

包括直方图、Box Plots、散点图、康托图、Parallel Coordinates、Star Plots、Chernoff Faces

Box Plots

包含Upper/Lower Extreme、Upper/Lower Quartile、Median、Outlier和Whicker。Outlier离群点在后面会有专门一章讨论

Parallel Coordinates

平行坐标将高维数据映射到一个N个纵坐标轴的折线，用于高维数据。类似的有Star Plots。

Dissimilarity matrix

相异度矩阵

对Nominal而言

$$
d(i, j) = \frac{total - match}{total}
$$

对Binary而言

令$q = (1, 1), r = (1, 0), s = (0, 1), t = (0, 0)$，分别表示对象$A$、$B$中属性值出现的四种对应情况的计数。

$$
dissimilarity = \frac{r + s}{total} \\
asymmetricBinaryDissimilarity = \frac{r + s}{q + r + s} \\
Jaccard = 1 - asymmetricBinaryDissimilarity
$$
原因是$(1, 1)$和$(0, 0)$有时不能同等看待，例如有时$(1, 1)$非常罕见。

对Numeric而言

曼哈顿距离（L1范数）和欧几里得距离（L2范数）分别是k为1和2的闵可夫斯基距离。$k \to \infty$是切比雪夫距离。

对Ordinal而言

首先进行排序，得到$x_{i, feature}$对应的排行$rank_{i, feature}$（从1开始），然后把排行归一化。
$$
z_{i, feature} = \frac{rank_{i, feature} - 1}{total_{feature} - 1}
$$

混合属性

$$
d(i, j) = \frac{\sum_{feature}{exsit_{i, j} d_{i, j}}}{\sum_{feature}{exsit_{i, j}}}
$$
其中$d_{i, j}$：
对Numeric是，相当于做个归一化
$$
\frac{|x_{i, feature} - x_{j, feature}|}{max_h(h, feature) - min_h(h, feature)}
$$
对Nominal是根据$x_{i, feature}$和$x_{j, feature}$是否相等取0或者1
对于Ordinal是先根据排名进行标准化，再按照Numeric的方法计算

Data Preprocessing

data cleaning、data integration、data reduction和data transformation是数据预处理的基本任务。
数据清洗包括缺失值、噪声、离群点和不一致问题的处理。数据集成包括对多种来源数据进行合并（实体识别），并处理其中的非一致和冗余数据。数据归约包含对维数和数量的归约。数据变换包括归一化、离散化和Concept Hierarchy Generation。

数据清洗

处理缺失值

忽略、人工填充、常数、填入全体中位数或均值、填入同类的中位数或均值、使用最可能的值填充（回归、贝叶斯算法等）。

处理噪声

根据分箱(binning)、回归、聚类（检测离群点）
分箱要求首先对数据排序，再划分为等频的箱，然后选择使用均值光滑（用均值替换箱中所有点）、边界光滑（用离自己最近的边界值替换）、中位数光滑等。
这些光滑噪声的手段常也被用作离散化和数据归约。

数据集成

可以通过相关性分析来检查数据冗余，例如对Nominal数据有$\chi^2$检验，对于Numeric数据有协方差和相关系数

$\chi^2$检验

卡方检验可以描述两个向量$A[1..m]$和$B[1..n]$的相似程度。
卡方检验的第一步是有一个数据集矩阵$M$，$M$中的元素$M_{ij}$，表示同时满足$A_i$和$B_i$性质的样本个数
将矩阵填入一张表中，在表的最右端和最下端扩充一列/行，用来记录对应行/列的总和

首先计算$e_{ij}$，也就是对应的列和乘以行和除以总数
$$
e_{ij} = \frac{sum(B = b_i) * sum(A = a_j)}{sum(all)}
$$

将它填在括号里面，再对于矩阵中所有的单元格计算

$$
\chi^2 = \sum_{m}{ \sum_{n}{ \frac{(x_{ij} - e_{ij})^2}{e_{ij}} } }
$$

皮尔逊相关系数

协方差可以衡量两个变量的总体误差，方差可以看做两个变量相同时协方差的特例
对于实数$X$、$Y$，定义协方差为
$$
Cov(X, Y) = E((X - \mathbb{E}(X))(Y -\mathbb{E}(Y)))
$$
对于向量$A$、$B$，定义协方差为

$$
Cov(A, B) = E((A - \bar{A})(B - \bar{B})) = \frac{\sum_{i = 1}^{n}{(A_i - \bar{A})(B_i - \bar{B})}}{n} = E(A * B) - \bar{A} \bar{B}
$$

皮尔逊相关系数为

$$
r_{A, B} = \frac{Cov(A, B)}{\sigma_A \sigma_B}
$$

注意这里分母标准差和分子期望中的$n$被约掉了，取值范围为$[-1, 1]$，等于0时变量独立，大于0时正相关，小于0负相关。
注意相关性不暗示因果性。

数据归约

小波分析

主成分分析

选取的主成分对应的坐标轴应当追求方差尽可能大

规范化数据
计算$k$个正交向量，即主成分。该过程可以对协方差矩阵求特征值和特征矩阵。
取出对应特征值最大的k个向量

标准化方法

min-max：
$$
v’_i = \frac{v_i - min_A}{max_A - min_A} (newMax_A - newMin_A) + newMin_A
$$
Z-score：
这里$\bar{A}$也可以替换成medoid或者mode等中心度量值，$\sigma_A$也可替换成absolute deviation$s$等离散程度度量值
$$
v’_i = \frac{v_i - \bar{A}}{\sigma_A}
$$
demical scaling：
$$
v’_i = \frac{v_i}{10^j} \quad where \\
\underset{j}{\mathrm{argmin}}(max(|v’_i|) < 1)
$$

Frequent Itemsets

Frequent Pattterns are patterns that appear frequently in a dataset
support：$A$和$B$同时出现的概率$p(A \cap B)$，可以是绝对的即出现次数，可以是相对的，再除以事务数
confidence：$p(B|A)$ = $c(A \cap B) / c(A)$
频繁项集指的是支持度满足最小支持度阈值$min_{sup}$的项集
闭频繁项集：$X$的任意超集$Y$的支持度不等于（小于）$X$的支持度
极大频繁项集：$X$是频繁的，并且没有任何$X$的超集$Y$是频繁的

下面使用Apriori算法和FP-Growth算法来发现频繁$k$项集，注意我们不关注频繁$k+1$项集，尽管在过程中我们可以作为一个子问题得到它。

Apriori算法

Apriori算法基于Apriori性质：频繁项集的子集一定是频繁的

使用Apriori生成频繁项集

使用频繁项集生成关联项集

对于所有的频繁项集$l$，生成$l$所有的非空子集
对于$l$的每个非空子集$s$，输出规则$s \rightarrow (l - s)$，如果满足$p(l|s) \ge min\_conf$

Apriori优化方法

Hash-based itemset counting：hash到多个桶里进行初步删选
Transaction reduction：删去不包含任何$k$项集的事务
Partitioning：任何在DB中可能频繁的项集，至少在一个DB分区中是频繁的
这个性质很有意思，假设将数据集$D$分成了$n$个不重叠的部分$D_1, .. D_n$，下面证明任何在$D$中频繁（相对最小支持度为$s$）的项至少在$D$的一个部分$D_i$中频繁。
使用反证法证明。设有一个项集$x$在$D$中频繁。则有
$$
support\_count(x \in D) / |D| \ge s
$$
而$x$在$D_1, .. D_n$都不频繁，则有
$$
\frac{ support\_count(x \in D_i) }{ |D_i| } \lt s
$$
有
$$
\sum_{i = 1}^{n}{ support\_count(x \in D_i) } \lt s , \sum_{i = 1}^{n}{ |D_i| }
$$
即
$$
\sum_{ i = 1 }^{ n } { \frac{ support\_count(x \in D_i) }{ |D| } } \lt s
$$
上面的式子就是
$$
n * support\_count(x \in D) / |D| < n * s
$$
与假设矛盾
Sampling：在给定数据集的子集中挖掘，降低支持度要求，并采用一些方法确定其完整性
Dynamic itemset couting：

FP-Growth

利用FP-Tree生成频繁项集

在建成FP-Tree后，从后往前生成频繁项集。以《数据挖掘：概念与技术(第3版)》为例，考虑最后的节点$I5$：

构造$I5$的条件模式基(prefix path sub-tree ending in $e$)
首先从$I5$的所有节点（可以是叶子节点也可以是内部节点，这里$I5$就都是叶子节点，而$I1$就有一个内部节点）往树根找到一条树链，将树链上的所有节点的支持度改为等于叶子节点$I5$的支持度
1
2
<I2, I1, I5 : 1>
<I2, I1, I3, I5 : 1>
接着提取出前缀路径，即条件模式基
1
2
<I2, I1: 1>
<I2, I1, I3 : 1>
使用条件模式基构造条件FP树
$I5$的条件FP树可以看做是原事务集中含有$I5$的所有项组成的集合，然后把里面的$I5$全部去掉
因此可以使用和构造FP树相同的办法
1
<I2, I1: 1>
注意此时$I3$被去掉了，因为它在条件FP树上的的支持度为1，不满足2的最小支持度。实际上指的是$(I2, I3, I5)$这个项集的支持度不足。
查看$I5$是否是频繁项集（可以由简单计数得到）
如果$I5$是频繁的，找到所有以$I5$结尾的频繁项集

Basic Classification

基本概念

训练集、测试集

决策树

决策树分为树枝，表示对特征测试的结果，由此产生子节点。子节点分为内部节点和叶子节点，叶子节点展示所属类的标签，内部节点展示被测试的特征
决策树不需要领域知识和数值参数，能够处理多维数据，学习结果直观
在设计决策树算法时需要考虑：如何确定特征测试条件（二类划分还是多类划分等）从而获得最佳切分（考量homogeneous/purity），什么时候可以终止切分（同类、早停）
如果决策树的一个节点下只有一个类，这个节点就是pure的

节点的信息熵

假设数据集$D$可被分为类$[1..n]$，定义节点$t$下的数据属于类$j$的条件概率是$p(j|t)$，即
$$
P(X = j) = p(j|t)
$$
由此可以定义信息熵为
$$
info(t) = entropy(t) = H(t) = -\sum_{j = 1}^{n}{p{(j|t)},log,p(j|t)}
$$

信息熵能够描述节点的homogeneity，当熵最大（$=log,n$）时意味着随机性越大，信息也就越少；当熵最小（=0）则相反。
所有数据从根节点可以通过所属的类分为$n$部分，这种关于类别的信息熵称为数据集的经验熵，如果不利用特征建立决策树，我们只能根据经验熵得到一个数据所属类别的概率。

$$
H_{j}(D) = - p(j),log,p(j) \\
H(D) = \sum_{j = 1}^{n}{ H_{j}(D) }
$$

也可以定义关于特征$A$的信息熵，其中特征$A$取值为$[1..n_A]$

$$
H_{A}(D) = \sum_{j = 1}^{n_A}{ H_{j}(D) }
$$

信息增益、信息增益比和基尼指数

决策树生成是一个递归的过程，通过测试父节点$t$的特征$A$，将其划分为$k$个子节点，其得到的经验条件熵要小于等于父节点集合的经验熵，产生的差值为信息增益。这是符合直觉的，特征$A$的信息应当能够减少分类的不确定程度。其中$n_i$表示特征$A$取值为第$i$种时对应的数据集大小，也可写作$|D_i|$，显然$D_1 + D_2 + .. + D_n$

$$
Gain_{split} = H(t) - \sum_{i = 1}^{k}{\frac{n_i}{n} H(i)}
$$

不过信息增益容易将结果分为很多个小类，因此提出了信息增益比的概念

$$
GainRatio_{split} = \frac{Gain_{split}}{ H_{A}(D) }
$$

基尼指数是用来度量impurity的，例如在节点$t$上。基尼系数熵之半的函数图像差别不大，但是计算要简单很多，所以很常用

$$
Gini = 1 - \sum_{j = 1}^k{p(j|t)^2}
$$

使用基尼系数分类具有相似的规则，同样是为了使得“增益最大”，所以可以求下面式子的argmax

$$
Gini_{split} = Gini(t) - \sum_{i = 1}^{k}{\frac{n_i}{n} Gini(i)}
$$
但通常而言是直接求argmin

$$
Gini_{split} = \sum_{i = 1}^{k}{\frac{n_i}{n} Gini(i)}
$$

当数据是均匀分布在所有类上时，基尼系数取最大值$1-1/n$，当数据值集中在一个类上时（更为有趣的信息），基尼系数取最小值0。

决策树训练

由周志华教授的《机器学习》P77，当信息增益出现平票时可以任意选择。此外还有一种情况，当最后没有其他属性，只能进行多数表决时，出现平票也是随便选。

欠拟合与过拟合

欠拟合表现为模型太简单，训练集误差(Re-substitution errors)和泛化误差(Generalization errors)都很大。
过拟合表现为模型对新数据的泛化能力较弱，模型过于复杂。
为了估算泛化误差，可以使用Reduced error pruning方法，即使用验证集来估算。
奥卡姆剃刀法则，复杂的模型有更大的几率是拟合了数据里面的误差，因此在选择模型时应当考虑模型复杂度。
常用的解决过拟合的办法有早停策略，对于决策树来说可以在决策树彻底生成前停止算法，即预剪枝；还可以在决策树生成后进行处理，例如后剪枝。

缺失值处理

贝叶斯分类器

朴素贝叶斯算法相对决策树和部分神经网络算法要快，对于大数据更准确，基于贝叶斯定理
$$
P(H|X) = \frac{P(X, H)}{P(X)} = \frac{P(X|H) P(H)}{P(X)}
$$

其中$X = (x_1, …, x_n)$是数据集中的一个向量，$H$是有关分类的假设，例如$P(C_i|X), i \in [1, m]$表示$X$为类$C_i$的概率。$P(H|X)$是后验概率，$P(H)$是先验概率。
对于未知向量$X$，朴素贝叶斯算法要求找到最大化$P(C_i|X)$的类$C_i$
$$
P(C_i|X) = \frac{P(X|C_i) P(C_i)}{P(X)} \quad for , i \in [1, m]
$$
其中$P(C_i)$来自先验假设或根据数量统计得到，$P(X)$也是先验的，是个常数，所以有的时候并不考虑这个分母。
在Class conditional independence假设下，$P(X|C_i)$计算变得简单很多，只需要对$X$中的每个属性$x_k$分别计算即可
$$
P(X|C_i) = \prod_{k = 1}^{n}{P(x_k | C_i)}
$$
例如计算$P([rain, hot, high] | Yes)$，就可以计算
$$
P(rain | Yes) , P(hot | Yes) , P(high | Yes)
$$
然后可以得到
$$
P(Yes | [rain, hot, high]) \propto (P(rain | Yes) , P(hot | Yes) , P(high | Yes)) P(Yes)
$$

分类评估

我们定义$TP$、$TN$、$FP$、$FN$分别为真正例、真反例、假正例、假反例。这里$T$、$F$表示预测和真实值是否相同，$P$、$N$表示我们的预测结果是正例还是反例。令$U = TP + TN + FP + FN$为样例总数
由此可以派生出一系列评价指标：
accuracy/recognition rate是所有的$T$比上总数$U$；error rate是所有的$F$比上总数$U$。衡量了整个分类器在正反例上的准确度。
查准率precision是$TP$比上预测结果中所有的$P$($ = TP + FP$)，也就是所有预测的正例中正确的比率。
查全率、敏感度recall为$TP$比上真实情况下所有的$P$($ = TP + FN$)，也就是所有正例中被预测出的比率
specificity是$TN$比上真实情况下所有的$N$，也就是所有反例中被预测出的比率
$F_1$值为precision和recall的调和平均

Holdout方法

包括交叉验证和留一法

Alternative Classification

支持向量机

神经网络

Lazy Learning

集成学习

Basic Clustering

聚类分析包含Partitioning、Hierarchical、Density-based和Grid-based方法。

k-means

k-means的目的是最小化簇内方差
$$
E = \sum_{i = 1}^{k}{ \sum_{p \in C_i}{EuclideanDistance(p, c_i)^2} }
$$
这个问题是NP难的，k-means使用的贪心的方法不保证最优解，其步骤是：

选择$k$个簇的中心
将数据点分配到距离最近的中心对应的簇
使用每个簇中点的均值更新中心
重复2-3直到收敛

初始值确定

一般可以取$k = \sqrt{n/2}$，或者使用Elbow method
$k$值确定后可以使用Sampling或Pick “dispersed” set of points（选择到已选点最小距离最大的点）方法来取出$k$个中心点

由此可以看出k-means方法对初始化很敏感。并且有的数据是没有定义均值的，这时候可以选择使用k-modes。此外k-means对离群点和噪音和敏感。

对于大数据集，可以采用采样、micro-clusters、additional data structure来实现scalability

k-medoids和PAM方法

由于k-means对噪声很敏感，所以引入了k-medoids，它并不是用均值，而是用数据集中的一个代表点来表示集群的中心

$$
E = \sum_{i = 1}^{k}{ \sum_{p \in C_i}{EuclideanDistance(p, o_i)^2} }
$$
如上式，$o_i$是簇$C_i$的代表点。该算法流程如下：

选取$k$个代表点
尝试使用非代表对象$o_{random}$替换代表点$o_1 .. o_k$，假设正在替换某代表点$o_j$，则更新其代价函数
对于所有的对象重新进行分配，并计算交换总代价。如果总代价小于0，则接受这次替换，否则维持$o_j$不变

对于大数据可使用CLARA、CLARANS等方法

agglomerative clustering

dendrogram图，类似一个从底部构建的二叉树。
Hierarchical Clustering的优点是不需要预测簇的数量，并且往往能和一些分类学的知识建立联系。
agglomerative方法是自底而上地不断merge，divisive方法是自定而上的不断split
基础的算法应用一个proximity matrix描述两个簇之间的相似度

agglomerative的方法也有缺陷，例如簇之间merge的结果不能取消，没有像kmeans一样针对目标函数优化，三种簇间距离的度量方法各有缺陷

度量两个簇之间的距离

两簇间最相近的两个元素的距离：对噪声和离群点敏感
两簇间最相异的两个元素的距离：减少了集群半径的增加，容易打破大的集群
每个点对间距离的平均：对噪声和离群点不那么敏感，Biased towards globular clusters

divisive clustering和最小生成树

DBSCAN

DBSCAN是基于密度的方法，将所有的点分为三类

Core
在集群中，且neighborhood是dense的（Eps-MinPts条件）
Border
在集群中，但neighborhood不dense
Outlier
不在集群中

可以做出下面的讨论

从$q$直接密度可达$p$
当$p$在$q$的Eps-neighborhood内，并且$q$是一个Core
从$q$密度可达$p$
存在对象链$p_1, .. , p_{n-1}, p$，其中$p_{i+1}$直接密度可达$p_i$
$p$和$q$密度连接
存在一点$o$从$p$和$q$都密度可达

因此算法流程如下：

标记所有节点为未读
选取随机未读节点$p$并标记
1. 如果$p$是一个Core，则包含所有密度可达$p$点的点$p’$建立一个新的簇
  如果$p’$未访问，把$p’$加入簇，并递归。
  如果$p’$已访问，但不属于任何簇（之前被标记为噪音了），把$p’$加入簇。
  通过以上的两点可以保证点$p’$如果在Eps-neighborhood内有一个Core点$q$，那么即使$p’$本身不是Core，在一开始被划为Noise，最后也能正确地被分到对应的簇中。
2. 否则标记$p$为噪声

DBSCAN对参数取值敏感

OPTICS

聚类评估

Clustering Tendency

数据集是否根据一个均匀分布产生的
Hopkin Statistics

Cluster Quality

外在方法

外在方法通过把聚类(cluster, $C$)和基本事实(catagory, $L$)比较

Cluster Homogeneity：簇的纯度
Cluster Completeness：如果在基于基本事实，两个对象属于同一catagory，那么他们应当属于同一个簇
Rag bag：翻译叫碎布袋，即一个异类的对象最好放入碎布袋中，而不是放入纯的簇中
Small cluster preservation：将小catagory再分成碎片是非常有害的，因为它使得这些小簇可能成为噪声
BCubed precision：
Correctness：等于1如果$L(o_i) = L(O_j) \Leftrightarrow C(o_i) = C(O_j)$
BCubed recall
BCubed precision

内在方法

内在方法通过比较簇之间分离的优劣
轮廓系数Silhouette coefficient，定义$a(o)$为对象$o$到所属簇中其他对象之间的平均距离，定义$b(o)$为$o$到$o$不属于的所有簇的最小平均距离。则
$$
s(o) = \frac{b(o) - a(o)}{max(a(o), b(o))}
$$

Alternative Clustering

高斯混合模型

在Fuzzy clusters和Probabilitic-model based clustering中，一个对象可以属于多个簇，按照对应的概率。
高斯混合分布属于生成模型，它可以描述数据是如何从模型中产生的。

EM算法：E步骤

EM算法：M步骤

Biclustering

对于高维数据，传统的基于距离的方法，例如基于欧几里得距离的方法是不可信的，容易被多个维度的噪音所掩盖。因此高维数据的聚类常常是用一小组属性来定义的。
常见有两种高维聚类的方式，第一类是Subspace clustering methods，在高维数据的一个子空间里面搜索聚类，常见的有Biclustering；第二类是Dimensionality reduction approaches，构造一个更低维数的空间，并且在那个空间里面搜索聚类，例如Spectral Clustering

Clustering with constraints

Outlier Analysis

离群点，相对于normal/expected data，是指距离其他对象显著远的对象。离群点不是噪音，噪音是没有研究价值的，类似于random error或者variance
离群点分为全局离群点（相对于其余数据）、情景离群点（相对于某些特定context的数据）和集体离群点。对集体离群点来说，里面的点单个考虑可能就不是离群点了。

统计学方法

参数法之Univariate Outlier Detection

Univariate Outlier Detection假设数据仅对一个指标服从正态分布。然后就可以使用3$\sigma$原则来检测一维离群点了（不过为啥要用极大似然估计呢）。
还可以使用之前学过的box plot来进行可视化估计，认为在$Q1 - 1.5 , IQR$以下和$Q3 + 1.5 , IQR$要上的点都是离群点
还可以使用Grubb’s检验（最大标准残差检验），与z-score有关

参数法之Multivariate Outlier Detection

Mahalanobis距离方法
$\chi^2$统计量

参数法之混合参数分布

非参数法之直方图

非参数法之Kernel Density Estimation(KDE)

基于邻近性的方法

距离方法

网格方法

密度方法

MapReduce

Cluster Computing架构：backbone between racks和rack between nodes
MapReduce是一种批处理算法，核心思想是Bring computation to data和Store files multiple times for reliability。

Map Reduce 的最关键之处在于 Shuffle，通过 Shuffle，具有相同 Key 的 KV 会被 schedule 到同一个节点上。
不妨考虑下面的问题，我们有很多个 key，每个 key 很大，内存中无法装下。如何计算出 topN 最多数量的 key？

外部排序
hash
这里的点是 hash 出来的 key 可能碰撞。这样会导致数量不准确。这里就必须记录一下对应 key 的位置，seek file 确认是否重复。如果发生重复，则需要重新 hash。
map reduce
用一种 hash 算法，这样所有相同的 key 都会到同一个桶里面。然后对这个桶进行处理。

Mining Streaming data

流处理查询主要有两种类型：Ad-hoc查询和Stading查询

流数据取样

Bloom Filter

我记得之前柳晗就和我讨论过这个算法。
布隆过滤器用来检测一个数是否在集合中，对于确定性的方法而言，这通常意味着对$log(n)$的时间复杂度进行常数优化，或者对哈希函数和哈希方法进行优化。但无论如何，空间开销是免不了的。
布隆过滤器牺牲了准确性，他可能造成FP假阳性，即可能认为没出现过的数出现过，但换来了空间性能的提高。
算法思想很简单，将$n$个输入送给$k$个哈希函数$h_1, .., h_k$，哈希函数的计算结果将依次按位或到一个长度为$n$的bitset中，因此这个bitset中的某一位只能从0变成1。
例如，假设此时bitset为$b_i$，现对于新输入$x$，判断是否出现过。然后把$x$依次送入$k$个哈希函数，如果$h_j(x) = a$，则将第$a$位设为1。注意到如果此时第$a$位为0，则说明$x$肯定没出现过，但反之不一定成立。

Bloom Filter算法分析

Bloom Filter时间空间复杂度相对于数据规模是常数，因此主要分析出现FP的概率。
FP的概率与1的密度有关，显然1越多，越容易出现碰撞，因此可以表示为$a^k$，其中$a$表示此时1占的比例，不过碰撞概率是要略低于这个值的。我们还可以这样理解，把FP的概率近似看做对元素$x_i$哈希后输出的$k$个位置上都是1的概率$p_1$（当然有可能是重复了）。为了方便计算，我们实际考虑截至$x_i$，某一位仍然是0的概率$p_0 = 1 - p_1$。
将任意一位从0变为1的概率相当于将$d$和飞镖随机扔向$t$个目标，这里的$d$相当于所有的$n$个输入通过$k$个哈希函数得到的$nk$个结果，$t$相当于bitset。目标$T_i$被指定飞镖集中的概率是$1/t$，因此所有的$d$个飞镖都没有击中目标$T_i$的概率就是$(1 - 1/t)^d$，由于$t$通常很大，可以将其改写为$e^{-d/t}$（重要极限）。

Bit Counting和DGIM算法

对一个01串，在线回答问题最近的$k <= N$位中有多少个1。朴素的方法需要$O(N)$的空间，每次查询需要花费$O(k)$的时间。
DGIM算法能够只储存$O(log^2N)$位，在$O(log N)$的时间复杂度内给出一个大概的值，误差在50%以内，并可以进一步缩小到任意eps。
算法思路是维护一个容量为$N$的线性队列，从队尾到队头按照1的个数将其划分为$m \approx O(log_2N)$个桶，每个桶中分别有$2^0, 2^1, .., 2^m$个1（0的数量不考虑）。为了方便讨论，定义桶的大小是桶里面1的数目。
因此我们容易看出这个线性队列具有下面的性质：

每个桶的最右（靠近队尾）端总是1
所有的1都在某个桶中；但是0不一定，可能在桶间
每种大小的桶最多容忍有两个

下面使用该线性队列回答开始的问题：
通过比较每个桶两端的位置与$k$的大小，找到$k$值所在的桶$b$，累加$b$右边所有桶的大小及桶$b$的一半大小，即为估计值。
下面考虑如何维护该线性队列，考虑接受一个新比特时

首先弹出队头，并更新队头所属的桶（如果属于某个桶的话），如果此时桶里已经没有1了，就删除这个桶
如果新比特是0，则不做任何处理
如果新比特是1，则从右至左检查是否破坏性质每种大小的桶最多容忍有两个，并进行合并处理

DGIM算法分析

首先可以看到我们实际上不要将整个线性表存下来，我们只需要记录每个桶两端的坐标即可，这样的坐标有$O(log_2N)$个。对于每个坐标，他的值域是$[0, n)$，因此我们需要$O(log_2N)$比特来表示它。注意由于$N$很大，所以不能理解成一个坐标用一个$O(1)$的常数空间（例如int）就好。
下面分析DGIM误差的上下界

流数据聚类和BDMO算法

Recommendation System

Content Based方法注意物品的属性，协同过滤方法注意物品与用户的关系

TF.IDF

考虑从文档中选择关键词来最好地概括文档，一个简单的想法是希望这个词出现的频率越来越高，这也就是TF。但其实这是不够的，因为很多助词，例如“也”、“是”这些词出现的频率很高，但却不能用来概括文档。这时候我们需要IDF来描述，也就是说一个词如果出现的文档数越多，它就越common，权重就越底。
$f_{ij}$为term$t_i$在文档$d_j$中出现的频率
定义$TF_{ij} = f_{ij} / max_k(f_{kj})$
$n_i$为出现term$t_i$的文档数
定义$IDF_i = log \frac{N}{n_i}$
由此可以计算得到
$TF.IDF = TF_{if} * IDF_i$

Content Filtering

Content Filtering首先对每一个item建立profile，这里的profile指的是一组属性。使用余弦相似度衡量user profile$c$和item profile$s$。
$$
u(c, s) = cos(c, s) = \frac{c.s}{|c||s|}
$$
这种方法的缺点是过于专门化，它从来不推荐在user’s content profile外面的item，并且人们可能具有多个兴趣爱好。
此外需要有效的办法去查找high utility的items，也就是相似度高的profile，这时候可以借助于Locality Sensitive Hashing。

Collaborative Filtering

协同过滤算法的基本思路是对于用户$c$，找到其他用户组$D$和$c$的对所有item的交集给出的评分相近，然后对于新的item，基于$D$的评分估计$c$的评分。
设$x$的评分向量为$r_x$，那么$x$，$y$的相似度可以用余弦相似度衡量$cos(r_x, r_y)$，也可以计算$sim$的的皮尔逊相关系数（仅对$x$、$y$都评分项计算）
下面使用协同过滤算法进行预测$c$给item$s$的打分。在给item$s$打分的用户里面找出$k$个最接近用户$c$的用户，令为$D$。则
$$
r_{cs} = \frac{1}{k \sum_{d \, in \, D}{r_{ds}}} \\
r_{cs} = \frac{ \sum_{d \, in \, D}{sim(c, d) \, r_{ds}} }{ \sum_{d \, in \, D}{sim(c, d)} }
$$
协同过滤算法的计算$D$是比较昂贵的，对于每个用户，需要线性的时间。此时我们可以同样借助Locality Sensitive Hashing。
此外可以使用MapReduce来计算协方差矩阵，我记得当时参加第一节云计算大赛的时候的技能题就有一条是这个。
刚才的算法是基于用户的，user-user协同过滤，也有item-item协同过滤，对于item$s$，找到相似的items，当然这里还是使用对相似item的rating而不是对用户的rating，因此可以使用相同的矩阵和预测函数。在实践上item-item的常优于user-user的。

Locality Sensitive Hashing

在之前提到的两种算法中提到了Locality Sensitive Hashing这个算法可以用来快速的找到高相似度的向量对（例如各种profile）
Locality Sensitive Hashing属于一种Approximate Nearest Neighbor Search方法
Locality-sensitive family是一组可以组合起来将向量按相似度区分开的函数。这些函数在统计上是彼此独立的。他们的速度要比遍历所有向量对来得快，并且能够被组合起来解决FP和FN问题。

$(d_1, d_2, p_1, p_2)$敏感表示：

如果$d(x, y) \le d1$，则$h(x) = h(y)$的概率至少为$p1$
如果$d(x, y) \ge d2$，则$h(x) = h(y)$的概率至多为$p2$

AND、OR of Hash functions

给定family$H$，从$H$中选择$r$个函数构造family$H’$。对于$H’$中的$h = [h_1, .., h_r]$：

$h(x) = h(y)$当且仅当对于任意的$i$都存在$h_i(x) = h_i(y)$
这是AND构造，指的是这$k$个哈希值里面要全部相同，才会被投影到相同的桶内
AND操作能够使得保持$p1$较大时$p2$更小，即降低FN
相应的定理是如果$(d_1, d_2, p_1, p_2)$敏感的，那么$H’$是$(d_1, d_2, p_1^r, p_2^r)$敏感的
$h(x) = h(y)$当且仅当对于存在一个以上$i$使得$h_i(x) = h_i(y)$
这是OR构造，指的是这$k$个哈希值里面有一对以上相同，就会被投影到相同的桶内
OR操作能够使得$p1$较小时$p2$更大，即降低FP
相应的定理是如果$(d_1, d_2, p_1, p_2)$敏感的，那么$H’$是$(d_1, d_2, 1-(1-p_1)^r, 1-(1-p_2)^r)$敏感的

Amplify LS family

考试内容2017

列出数据的种类（Nominal等）。解释Mean、Medoid等。
简述缺失值处理方法。简介PCA。
简述支持度等概念。证明Apriori性质。
比较Apriori和FP-Growth的性能。使用Apriori计算频繁项集。
为什么Naive Bayes是Naive的。如何基于Gini系数构建决策树。
使用BP计算神经网络
k-means有哪些缺点。DBScan。什么是dendrogram，如何度量两个簇的距离
协同过滤和内容过滤的区别是什么。什么是$(d_1, d_2, p_1, p_2)$敏感。证明（类似Excecise 2）。