数据挖掘简易复习

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

Intro

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

  1. Valid: hold on new data with certainty
  2. Novel: non-obvious to the system
  3. Useful: should be possible to act on the item
  4. 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负相关。
注意相关性不暗示因果性。

数据归约

小波分析

主成分分析

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

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

标准化方法

  1. min-max:
    $$
    v’_i = \frac{v_i - min_A}{max_A - min_A} (newMax_A - newMin_A) + newMin_A
    $$
  2. Z-score:
    这里$\bar{A}$也可以替换成medoid或者mode等中心度量值,$\sigma_A$也可替换成absolute deviation$s$等离散程度度量值
    $$
    v’_i = \frac{v_i - \bar{A}}{\sigma_A}
    $$
  3. 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生成频繁项集

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

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

Apriori优化方法

  1. Hash-based itemset counting:hash到多个桶里进行初步删选
  2. Transaction reduction:删去不包含任何$k$项集的事务
  3. 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
    $$
    与假设矛盾
  4. Sampling:在给定数据集的子集中挖掘,降低支持度要求,并采用一些方法确定其完整性
  5. Dynamic itemset couting:

FP-Growth

利用FP-Tree生成频繁项集

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

  1. 构造$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>
  1. 使用条件模式基构造条件FP树
    $I5$的条件FP树可以看做是原事务集中含有$I5$的所有项组成的集合,然后把里面的$I5$全部去掉
    因此可以使用和构造FP树相同的办法

    1
    <I2, I1: 1>

    注意此时$I3$被去掉了,因为它在条件FP树上的的支持度为1,不满足2的最小支持度。实际上指的是$(I2, I3, I5)$这个项集的支持度不足。

  1. 查看$I5$是否是频繁项集(可以由简单计数得到)
  2. 如果$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使用的贪心的方法不保证最优解,其步骤是:

  1. 选择$k$个簇的中心
  2. 将数据点分配到距离最近的中心对应的簇
  3. 使用每个簇中点的均值更新中心
  4. 重复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$的代表点。该算法流程如下:

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

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

agglomerative clustering

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

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

度量两个簇之间的距离

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

divisive clustering和最小生成树

DBSCAN

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

  1. Core
    在集群中,且neighborhood是dense的(Eps-MinPts条件)
  2. Border
    在集群中,但neighborhood不dense
  3. Outlier
    不在集群中

可以做出下面的讨论

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

因此算法流程如下:

  1. 标记所有节点为未读
  2. 选取随机未读节点$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$)比较

  1. Cluster Homogeneity:簇的纯度
  2. Cluster Completeness:如果在基于基本事实,两个对象属于同一catagory,那么他们应当属于同一个簇
  3. Rag bag:翻译叫碎布袋,即一个异类的对象最好放入碎布袋中,而不是放入纯的簇中
  4. Small cluster preservation:将小catagory再分成碎片是非常有害的,因为它使得这些小簇可能成为噪声
  5. 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。

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$肯定没出现过,但反之不一定成立。


例如,假设此时bitset为$b_i$,现对于新输入$x$,判断是否出现过。创建一个新的bitset为$b_{i+1}$,并memset为0,然后把$x$依次送入$k$个哈希函数,将哈希的结果按位或到$b_{i+1}$上。接着比较$b_i \& b_{i+1}$。如果不等于$b_{i+1}$,那么肯定没有出现过。但是如果相等,并不一定就真的出现,可能两个数对$k$个哈希函数的输出都一样。

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
  2. 所有的1都在某个桶中;但是0不一定,可能在桶间
  3. 每种大小的桶最多容忍有两个

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

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

DGIM算法分析

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

流数据聚类和BDMO算法

Recommendation System

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

TF.IDF

$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)$敏感表示:

  1. 如果$d(x, y) \le d1$,则$h(x) = h(y)$的概率至少为$p1$
  2. 如果$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]$:

  1. $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)$敏感的
  2. $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

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