Notes on 数据挖掘

2019-06-28 本文已影响0人清筱筱

绪论

数据的特点：有效、有用、非直观

邦弗朗尼原理：避免过度挖掘

聚类

K-Means

基本流程

选择类的数目
- 根据最终类的平均半径选取
初始化每个类：选取一个点作为中心
- 随机选取一个点，然后尽量发散地选取其它点
将每个点放入到类中心最近的类
调整每个类的中心
重复3~4

目标函数

$J(label,\mu) = \sum_{i=1}^m dis^2(x^{(i)}-\mu^{(i)}_{label})$

计算复杂度

线性

例：BFR算法-在高维欧式空间进行聚类

基本假设

簇是以簇心为期望的正态分布

三种对象

废弃集、压缩集（迷你簇）、留存集

基本流程

加载一个块到内存
将块中离类中心足够近的点放入该类并放入废弃集
- 马氏距离 $\sqrt{\sum_{i=1}^d(\dfrac{p_i-c_i}{\sigma_i})^2}$
将其他点与留存集内的点进行聚类，并将这些类加入压缩集
调整每个类的类中心
将距离近的压缩集合并
重复1~5，直到最后一轮
将压缩集和留存集放入最近的簇

层次聚类

分裂式、合并式

非线性聚类

在复杂数据下被经常使用

社区网络

模块度（Modularity）算法

目的

选取社区个数

目标函数

$Q(G,S)=\frac{1}{2m}\sum_s\sum_u\sum_v(A_{uv}-\frac{k_uk_v}{2m})$

$A_{uv}$ ：相连为 1，不相连为 0

$k$ ：顶点度数
$\dfrac{k_uk_v}{2m}$ ： $u$ 和 $v$ 间变的期望数量

归一化割（Normalized-cut）算法

目标函数

$ncut(A,B)=\frac{cut(A,B)}{vol(A)}+\frac{cut(A,B)}{vol(B)}$

优点

相比最小割，可以使得分割后的社区网络大小更加平衡

数据流挖掘

基本策略

查找近似解，侧重最近的样本点信息

数据抽样

固定比例（fixed proportion）

hash算法

固定大小（fixed size）

蓄水池算法（Reservoir Sampling）

基本流程
1. 选定蓄水池大小为 $k$
2. 将前 $k$ 个数据放入蓄水池
3. 对于第 $n=k+i$ 个数据，以 $\dfrac{k}{n}$ 的概率随机替换蓄水池中的元素
证明：算法可以抽取精确比例的样本
1. 当 $n=k$ 时，每个元素选中概率为 1。
2. 假设 $n = s$ 时，每个元素被选中概率为 $\dfrac{k}{s}$
3. 当 $n=s+1$ 时，蓄水池中元素被保留的概率为
  $\frac{k}{s}(\frac{s+1-k}{s+1}+\frac{k}{s+1}\frac{k-1}{k})=\frac{k}{s+1}$
  第 $s+1$ 个元素加入蓄水池的概率也为 $\dfrac{k}{s+1}$
4. 由数学归纳法，抽取比例为 $\dfrac{k}{n}$

窗口计数

DGIM算法

基本流程

利用桶（bucket）对滑动窗口进行划分
- 每个桶保存以下信息
  - 桶的大小，该数目为2的幂
  - 桶的最右边位即最后进入流的位的时间戳
  - 桶中1的个数
- 对滑动窗口进行划分时遵循以下5条规则
  - 桶最右边的位必须是1
  - 1个位最多属于1个桶
  - 每种大小的桶有1个或者2个
  - 每个桶的大小是2的幂
  - 桶的大小从右到左非降序排列
有新加入的位时，对桶进行更新
- 如果最左边的桶已经没有处于窗口中的位，则丢弃这个桶
- 新加入的位如果其为0，则无操作；否则建立一个包含新加入位的大小为1的桶
- 从右往左将连续出现三个相同大小的桶的左边两个进行合并
查询最近位
- 寻找含查询位的最左的桶 $b$
- 查询结果为 $b$ 右边所有桶包含1的数量总和，加上b的大小的一半

估计值误差（fractional error）

至少是正确值的50%：最差情况b中都是1
最多超过正确值的50%：最差情况b只有最右边一位为1

PageRank

基本流程

所有网页初始值为 $r^{(0)}=\dfrac{1}{N}$
使用幂迭代（Power Iteration）直到收敛
$r^{(t+1)}=\sum_{i\to j}\frac{r^{(t)}_i}{d_i} \\ r^{(t+1)}=Mr^{(t)}$
- 证明：幂迭代可以计算出 $M$ 的主特征向量
  
  设 $M$ 有 $n$ 个特征向量分别为 $x_1,x_2,…,x_n$ ，分别对应特征值 $\lambda_1,\lambda_2,…,\lambda_n$
  
  不失一般性假设 $\lambda_1>\lambda_2>…>\lambda_n$
  $\begin{align} r^{(0)}&=c_1x_1+c_2x_2+\dots+c_nx_n\\\\ Mr^{(0)}&=M(c_1x_1+c_2x_2+\dots+c_nx_n)\\ &=c_1\lambda_1x_1+c_2\lambda_2x_2+\dots+c_n\lambda_nx_n\\\\ M^kr^{(0)}&=M(c_1x_1+c_2x_2+\dots+c_nx_n)\\ &=c_1\lambda_1^kx_1+c_2\lambda_2^kx_2+\dots+c_n\lambda_n^kx_n\\ &=\lambda_1^k[c_1x_1+c_2(\frac{\lambda_2}{\lambda_1})^kx_2+\dots+c_n(\frac{\lambda_n}{\lambda_1})^kx_n] \end{align}$
  由于 $\dfrac{\lambda_i}{\lambda_1}<1(i=2,3,…,n)$
  
  当 $k\to +\infty$ 时 $(\dfrac{\lambda_i}{\lambda_1})^k \to 0$ ，则 $M^kr^{(0)} \to c_1\lambda^k_1x_1$

终止点与采集器陷阱

终止点

没有出链的网页

采集器陷阱

一系列没有指向集合之外的节点的集合

抽税法

进行随机跳转（teleport），避免终止点和采集器陷阱
$r^{(t+1)}=\beta\sum_{i\to j}\frac{r^{(t)}_i}{d_i}+(1-\beta)\frac{1}{N} \\ r^{(t+1)}=\beta Mr^{(t)}+(1-\beta)[\frac{1}{N}]_{N\times N}$

在线广告

在线二分图匹配

最大匹配

极大匹配（Maximal Matching）：在当前已完成的匹配下，无法再增加匹配边的匹配

最大匹配（maximum matching）：所有极大匹配当中边数最大的一个匹配

完全匹配

所有的顶点都是匹配点的匹配

贪心算法

优先匹配最大收益的边

竞争率

在最差的情况下，在线算法匹配数与离线算法匹配数之比

证明：贪心算法竞争率 $c\geq\dfrac{1}{2}$

设 $M_{opt}$ 为最大匹配， $M_{greedy}$ 为贪心算法匹配

$L$ 为在 $M_{opt}$ 中匹配但在 $M_{greedy}$ 中不匹配的左节点的集合， $R$ 为 $L$ 中所有左顶点所连接的右顶点的集合

可以得到
$\begin{gather} |M_{opt}|\leq|M_{greedy}|+|L|\tag{1}\\ |L|\leq|R|\tag{2}\\ |R|\leq|M_{greedy}|\tag{3} \end{gather}$
由 $(2)(3)$ 可得到 $|L|\leq|M_{greedy}|$ ，再结合 $(1)$ 可以得到 $|M_{opt}|\leq2|M_{greedy}|$ ，即
$c=\frac{|M_{greedy}|}{|M_{opt}|}\geq\frac{1}{2}$