网络数据挖掘课程笔记

Overview

搜索/广告-徐

• 置信度、支持度
• 决策树
• 监督学习评价指标：Accuracy/Precision/Recall/F1
• SVD 分解
  • Fold-in 算法
• AdaBoost算法
• BM25
• 语言模型Language Model for IR(LM4IR)、平滑化
• 排序学习：基于有序对
• 排序学习评价方法：MAP、NDCG(Normalized Discounted Cumulative Gain)
• TF-IDF计算公式
• 线性感知器
• SVM
  • 硬边距：
  • 软边距: 松弛变量$\xi$、参数$C$

图数据挖掘-沈

• 无标度网络：数据分布
• 复杂网络的小世界特性
• 连边关系的结构平衡
• 影响最大化问题
• PageRank
• 图聚类算法：Normalized Cut、模块度优化、InfoMap、非负矩阵分解等

推荐系统-罗

• 矩阵分解的核心思想
• 矩阵分解和U-U CF、I-I CF的区别
• U-U CF 的评分
• 相关度的度量：Pearson Correlation

关联规则

• 支持度和置信度: 对规则定量描述；
  • 支持度sup：$T$中交易同时包含$X$和$Y$的百分比(概率)
    $$
    \begin{align*}
    \mathrm{sup}=\mathrm{Pr}(X\cup Y)=\frac{\left|{ t\in T|X\cup Y\subseteq t}\right|}{\left|T\right|}
    \end{align*}
    $$
  • 置信度conf: $T$中包含$X$的事物同时包含$Y$的百分比
    $$
    \begin{align*}
    \mathrm{conf}=\mathrm{Pr}(X|Y)=\frac{\left|{ t\in T|X\cup Y\subseteq t}\right|}{\left|{ t\in T|X\subseteq t}\right|}
    \end{align*}
    $$
• 关联规则挖掘目标：找到最小支持度和最小置信度的规则
  给定交易集合$T$、最小支持度mincup、最小置信度minconf的情况下，$T$中存在唯一的关联规则集合
• Apriori算法
  • 相关概念、性质：
    • 频繁集：满足最小支持度的项目集合
    • 向下闭包性质：频繁集子集也是频繁集
  • 步骤：
    1. 寻找所有满足最小支持度mincup的频繁集
    2. 寻找频繁集产生规则

监督学习

• 分类模型评价准则

	预测为正	预测为负
标注为正	TP(true positive)	FN(false negative)
标注为负	FP(false positive)	TN(true negative)

评价准则	􏰮语言描述	􏰏数学公式
Accuracy	$\frac{正确分类􏰟􏰩总样}{总样本}$	$\frac{TP+TN}{TP+FN+FP+TN}$
Precision	$\frac{正确预测的正样本数}{预测为正例的样本数}$	$\frac{TP}{TP+FP}$
Recall	$\frac{正确预测的正样本数}{标注的正样本数}$	$\frac{TP}{TP+FN}$
F1	$和平均值$	$2\times \frac{Precision\times Recall}{Precision+Recall}$

• 分类算法：决策树
  • 贪心训练算法：
    • 自顶向下递归建树
    • 初始状态：所有训练数据都在跟节点上
    • 根据特征划分训练数据
    • 根据信息增益选择特征：
  • 训练终止条件：
    • 节点上所有训练样本都属于同一类别
    • 节点上无训练样本或无特征可选
  • 信息增益的计算
  • 剪枝方案
    • Pre-pruning
    • Post-pruning
• 分类算法：线性分类器 $f(\mathbf{x})=\mathbf{wx}+b$
  • 感知器(Perceptron): $yf(\mathbf{x}) \ge 0$
    • 迭代: $\mathbf{w}\gets \mathbf{w}+\eta y_i\mathbf{x_i}$、$b\gets b+\eta R y_i$，这里$R=\max_i|\mathbf{x}_i|$
  • Perceptron with Margin: $yf(\mathbf{x})\ge \tau$
  • SVM
    • 分类边距的计算
      $$\begin{align*}
      \because\begin{cases}
      \mathbf{wx}^{+}+b=+1\
      \mathbf{wx}^{-}+b=-1\
      \end{cases}\
      \therefore\langle\mathbf{w}, \mathbf{x}^{{+}-\mathbf{x}}{-}\rangle=2\
      \end{align*}$$
      根据点$\mathrm{x}_0$到超平面$\mathbf{wx}+b=0$的距离公式:
      $$\begin{align*}
      \mathrm{dist}=\frac{|\mathbf{wx}_0+b|}{\lVert\mathbf{w}\rVert}, \mbox{ here } \lVert\mathbf{w}\rVert=\sqrt{\langle\mathbf{w}, \mathbf{w}\rangle}
      \end{align*}$$
      计算$\mathbf{x}^{{-}$到超平面$\mathbf{wx}}{+}+b=+1$的距离：
      $$\begin{align*}
      \mathrm{dist}&=\frac{|\mathbf{wx}^{-}+b-1|}{\lVert\mathbf{w}\rVert}\
      &=\frac{2}{\lVert\mathbf{w}\rVert}
      \end{align*}$$
    • SVM 原始优化问题
      故最大化$\mathrm{dist}=\frac{2}{\lVert \mathbf{w}\rVert}\Longleftrightarrow$最小化$\frac{1}{2}\lVert \mathbf{w}\rVert^2$
      $$\begin{align*}
      \max_{\mathbf{w},b} \frac{2}{\lVert\mathbf{w}\rVert}\Rightarrow\min_{\mathbf{w},b} \frac{1}{2}\lVert\mathbf{w}\rVert^2\
      \mbox{s.t. }\quad y_i(\mathbf{w}x_i+b)\ge 1,\quad i=1,2,\cdots,N
      \end{align*}$$
    • Soft-Margin SVM原始优化问题
      $$\begin{align*}
      &\min_{\mathbf{w}} \frac{1}{2}\lVert\mathbf{w}\rVert^{2+C\sum_{i=1}}N\xi_i\
      &\mbox{s.t. }\quad y_i\mathbf{wx}_i\ge 1-\xi_i,\quad \xi_i\ge 0, i=1,2,\cdots,N
      \end{align*}$$
      • **Tips：**这里使用了增广权向量$\mathbf{w}$、增广向量$\mathbf{x}$。
      • 松弛变量 $\color{red}\xi$ 表示不满足$y_i\mathbf{wx}_i>1-\xi_i$的数据距离当前分类边界的距离，用来量化偏离的程度，也就是错误的大小。松弛变量$\xi_i> 0$表示样本点$(x_i,y_i)$是一个离群点；对于分类器正确分类样本点$(\mathbf{x}_i,y_i)$，其对应的$\xi_i=0$
      • 超参数 $\color{red}C$ 权衡边距大小与错误容忍度，$C$变大，牺牲边距，减少训练集上的错误。可以通过交叉验证或者验证集确定$C$的值，$C$值越大，越容易过拟合。
    • Soft-Margin SVM对偶优化问题
      $$\begin{align*}
      \max_{\alpha_1,\cdots,\alpha_N}\sum_{i=1}^{{N}\alpha_i-\frac{1}{2}\sum_{k=1}}{N}\sum_{l=1}^{N}\alpha_k\alpha_ly_ky_l\langle\mathbf{x}_k,\mathbf{x}l\rangle\
      \mbox{s.t. }\quad \begin{cases}\quad \sum{i=1}^Ny_i\alpha_i=0\
      0\le \alpha_i\le C, \quad i=1,2,\cdots,N
      \end{cases}
      \end{align*}$$
      $\alpha_i\gt 0$: $\mathbf{x}_i$是支持向量
    • 对偶问题求解算法：SMO
• 损失函数
  • 回归：最小二乘
  • 二值分类
    • 0-1 Loss
    • Hinge Loss: $L(f(\mathbf{x}, y))=\max(0, 1-yf(\mathbf{x}))$
    • Exp Loss: $L(f(\mathbf{x}, y))=\exp(-yf(\mathbf{x}))$
    • Logistic Loss：$L(f(\mathbf{x}, y))=\log(1+\exp(-yf(\mathbf{x})))$
• AdaBoost

  • AdaBoost算法
    Adaboost

  • AdaBoost 的损失函数

    • 指数损失函数
      $$\begin{align*}
      E_{0-1}&=\frac{1}{N}\sum_{i=1}^{N}{f_T(\mathbf x_i)\ne y_i}\
      &=\frac{1}{N}\sum_{i=1}^{N}\exp{-y_if_T(\mathbf x_i)}=L(f_T)
      \end{align*}$$
    • 指数损失函数是0-1损失函数的上界

  • AdaBoost 加性模型

• 结构化输出
  • 结构化输出预测模型定义
  • 训练方法：数据转化+二分类
  • Structured Perceptron
  • SVM-struct
    • 原优化问题
    • 对偶优化问题
  • 变边距SVM-struct

无监督学习

• 聚类算法：K-Means
  • 算法步骤
    K-Means
  • 终止条件
  • 优点
  • 缺点
    K-Means Drawbacks
  • 聚类算法评价方法
    • 间接评价
    • 直接评价
      K-Means Evaluation
      K-Means Evaluation
• 矩阵分解：高维矩阵的低秩近似

大规模机器学习

• 数据并行
• 模型并行
• 数据并行+模型并行
  • 参数更新方案
    • 同步更新Bulk Synchronous Parallel(BSP)：设置同步点。同步点的设置导致BSP低效。
    • 异步更新：完全没有参数同步。
    • 半同步更新Stale Synchronous Parallel(SSP)：设置执行最快和最慢的节点间轮数的最大差异。优点：比同步快，比异步结果更加准确。
• 参数服务器（Parameter Server）

排序学习

• 传统相关性排序模型
  • 向量空间模型(Vector Space Model, VSM)：tf-idf+Cosine Similarity
  • BM25
    $$\begin{align*}
    \mathrm{BM25}=\sum_{i\in q}\log\frac{N}{\mathrm{df}_i}\frac{(k_1+1)\mathrm{tf}_i}{k_1\left((1-b)+b\frac{\mathrm{dl}}{\mathrm{avdl}}\right)+\mathrm{tf}_i}
    \end{align*}$$
    • $\mathrm{avdl}$: 文档平均长度
    • $k_1$: 控制因$\mathrm{tf}$的增大最终排序值的速度
    • $b$: 控制文档长度归一化程度
• 排序评价指标
  • 基于二值相关度标签：Precision at K(P@K)、Mean Average Precision(MAP)
  • 基于多值相关度标签：Normalized Discounted Cumulative Gain(NDCG)
    $$\begin{align*}
    \mathrm{Gain}&=2^{\mathrm{label}}-1\
    \mathrm{DCG@N}&=\sum_{i=1}^{N}\frac{\mathrm{Gain}i}{\log(\mathrm{rank}+1)}\
    &=\sum{i=1}^{N}\frac{2{\mathrm{label}_i}-1}{\log(\mathrm{rank}+1)}
    \end{align*}$$
    • $\mathrm{label}$: 相关性程度标签
    • $\mathrm{NDCG}$: 根据最优排序对$DCG@N$进行归一化
• 排序学习算法
  • Point-wise Approach: 排序问题$\rightarrow$查询-文档作为训练样本，形式化为分类/回归问题
  • Pair-wise Approach: 排序问题$\rightarrow$文档有序对上的二值分类问题
    • Ranking SVM
  • List-wise Approach

User-User/Item-Item Collaborative Filtering

• Goal: To predict the rating $p_{ui}$ of user $u$ on item $i$

• User-User CF

• Item-Item CF

  1. Picking Item Neighbors $N$: The intersection of Itemset_u and Neighbor_i

     • Itemset_u: the set of items user u has rated
     • Neighbor_i: the set of items which are top-k similar to item i

  2. Scoring Items
     $$p_{ui}=\frac{\sum_{j\in N} \mathrm{sim}(i, j)r_{uj}}{\sum_{j\in N}|\mathrm{sim}(i,j)|}$$

     • how to calculate $\mathrm{sim}(i, j)$?
       • Normalization first: subtract item mean
       • Cosine similarity

     向量中心化+Cosine Similarity=Pearson 相关系数

Matrix Factorization

• FunkSVD: $R=UV^T$
  • 用户-物品评分矩阵$R$: $m\times n$
  • 用户隐空间矩阵$U$: $m\times k$
  • 物品隐空间矩阵$V$: $n\times k$

图排序

• 复杂网络
  • 小世界网络:高聚集性和短直径并存
  • 无标度网络:度分布服从幂率
• 图排序即按照节点重要度进行排序：度中心度、介数中心度、距离中心度、谱中心度、…
• 图排序算法：PageRank
  PageRank
  PageRank Converage
  • PageRank 收敛的充分条件
    • 任意2点可达
    • 非周期
    • 不可约简
• 图排序算法：HITS

图挖掘/图聚类

• 图划分

  • 最小割Min-Cut 划分
    • 拓展1: Ratio Cut
    • 拓展2: Normalized Cut(NCut)
      $$\begin{align*}
      \mathrm{NCut}(\mathbf{C})&=\frac{1}{2}\sum_{i=1}^{K}\frac{W(\mathbf{C_i},\bar{\mathbf{C}_i})}{\mathrm{vol}(\mathbf{C_i})}\
      \mathrm{vol}(\mathbf{C}i)&=\sum{u\in \mathbf{C}i}\sum_v A{uv}
      \end{align*}$$
  • 贪心/局部算法：KL 算法(Kernighan-Lin)
  • 全局方法：谱划分

• 谱划分/谱聚类

  定义矩阵$A$为$n$个顶点的无向图的邻接矩阵/边权非负矩阵，矩阵$D$是对角矩阵，且$D_{ii}=\sum_{j}A_{ij}$表示节点$i$的度数/边权和。
  定义$L=D-A$，矩阵$L$就是矩阵$A$的对应的**Laplace 矩阵**。

  • Laplace 矩阵的性质:
    • 对于任意向量$x$，都有$x^{TLx=\frac{1}{2}\sum_{i,j}A_{ij}(x_{i}-x_{j})}2$
    • 半正定，即$0=\lambda_1\le\lambda_{2}\le\dots\le\lambda_{n}$
  • 证明：
    $$\begin{align*}
    x^TLx &= x^T(D-A)x=xTDx-x^TAx\
    &= \sum_{ij}x_ix_jD_{ij}-\sum_{ij}x_ix_jA_{ij}\
    &= \sum_{i}x_i^2D_{ii}-\sum_{ij}x_ix_jA_{ij}\
    &= \sum_{ij}(x_i^2-x_ix_j)A_{ij}\
    &= \frac{1}{2}\sum_{ij}(x_i^2+x_j2-2x_ix_j)A_{ij}\
    &= \frac{1}{2}\sum_{ij}(x_i-x_j)^2A_{ij} \ge 0
    \end{align*}$$
    显然，当$x_{1}=x_{2}=\dots=x_{n}=\frac{1}{\sqrt{n}}$时，$x$是$L$的一个特征向量，且对应的特征值为$0$。
  • 谱聚类算法的一般步骤：
    • 通过$n$个数据点构造无向图。无向图中的节点对应数据点，按照数据点的近邻+相似度规则构造出邻接矩阵$A$；
    • 计算无向图的度矩阵$D$，$D$是对角矩阵，对角元素的值为邻接矩阵$A$对应行的行和;
    • 计算Laplace矩阵$L=D-A$;
    • 对Laplace矩阵$L$进行特征值分解，取前$k$小的特征值及其对应的特征向量$(k
    • 将数据点映射到$k$维空间中，在$k$维空间中，对所有变换之后的样本点采用K-Means聚类，聚类结果就是谱聚类之后的结果。

  谱聚类的基本思想便是利用样本数据之间的相似矩阵（拉普拉斯矩阵）进行特征分解（ 通过Laplacian Eigenmap 的降维方式降维），然后将得到的特征向量进行 K-means聚类。
  此外，谱聚类和传统的聚类方法（例如 K-means）相比，谱聚类只需要数据之间的相似度矩阵就可以了，而不必像K-means那样要求数据必须是 N 维欧氏空间中的向量。
  spectral-clustering
  spectral-clustering

• 图划分 vs. 社区发现

  • 图划分
    • 按照任务需求对网络进行划分
    • 划分的分量数通常已知
    • 各个分量彼此不重叠
  • 社区发现
    • 寻找网络固有的结构规则
    • 社区个数通常未知
    • 社区可以重叠、嵌套

• 模块度
  Module

• InfoMap
  将编码问题变成社区发现的对偶问题，寻找网络最优二级编码对应网络社区发现。

• 图嵌入
  图嵌入目标是是图数据从高维稀疏的非欧空间嵌入到一个低维的欧式空间，保持某些性质不变。

  • 非负矩阵分解NMF
    原始高维空间近似映射到低维空间
  • 其他：DeepWalk、LINE、SDNE

图预测

• 两类信息传播模型
  • 阈值模型：线性阈值模型
    • 有记忆性：根据邻居节点情况来判定当前节点是否被激活
  • 级联模型：独立级联模型
    • 顺序无关：有多个节点尝试激活同一个节点时，按照任意顺序进行
    • 无记忆性：节点$u$成功激活$v$的概率只和$p_{uv}$有关，和历史上有多少节点尝试激活节点$v$无关
    • 传播具有很大的随机性
    • 通过蒙特卡罗模拟得到多次传播的范围，取平均值
    • 缺点：计算不同节点的影响范围时，对于每个节点需要重新进行蒙特卡罗模拟
• 影响最大化
  influence-maximization
  • 性质
    • 非负性
    • 单调性
    • 次模性：边际效益递减
• 网络推断问题：根据信息传播记录(information cascade)，推断背后的传播网络(节点之间的传播概率)
  • 点对型模型
  • 改性型点对型模型：每个用户采用两个低维(k)向量表达。
    • $I$: 表示节点的影响力(influence)
    • $S$: 表示节点的易感度(susceptibility)
    • 用户间的人际影响力建模为: $p_{uv}=I_uS_v$
    • 减少模型参数，克服了点对型模型的过表达和过拟合问题
• 流行度预测：幂律分布
  • 基于时序：流行度在时间上呈现对数自相关性
  • 基于结构多样性
  • 基于自增强泊松过程的流行度预测：
    • 富者愈富、适者生存、老化效应
    • 指数上升、幂率衰减

References

[1]. Jun Xu, Ping Luo, Huawei Shen. Web Data Mining Slides.