Chapter 14. Unsupervised Learning
作者竟然把无监督学习放在了一整章节,显示除了一位统计学者的偏好。本次内容比较长,准备两三天读完该章节。另外发现一个问题,当作者以文字叙述、用各种词汇描述解释时,我就看不懂了。这个时候,说明作者也不太精通,做不到“深入浅出”。。。
Association Rules 又叫 Market Basket Analysis。嗯,起源于市场分析用户的购物习惯,找到同时购买几件物品的关联性,然后做出推荐、促销。20年前,亚马逊已经用于他们的购物网站了。Conjunctive rule 的定义:在所有的 $S_j$ 可能值中,找到一个他的子集 $s_j$,让变量 $X_j$ 在该子集的概率足够大;然后找到所有 p 维子集的一个集合,如果集合的概率相对足够大,则为一个 rule。集合的概率定义如下: $$\Pr \left[ \bigcap_{j=1}^p (X_j \in s_j)\right]$$ 相关术语,如果找到一个 association rule:$A \Rightarrow B$, 即买 A 就很可能买 B,
Apriori Algorithm 遍历所有的可能组合,同时通过 hard decision 删除所有概率低于阈值的组合。Apriori 基于一个很强的假设,做个比喻:
给定三个变量 A,B 和 C,如果 $\Pr(ABC)>0.2$,那么必须满足 $\Pr(AB)>0.2$, $\Pr(AC)>0.2$ 且 $\Pr(BC)>0.2$。注意,A, B, C 并不是相互独立的。不然我们就不用找 rule 了。
Apriori 给定的规则是:
\begin{align} W(C) =& \frac{1}{2} \sum_{k=1}^K \sum_{C(i)=k}\sum_{C(i'=k)} \|x_i - x_{i'}\|^2 \\ =& \sum_{k=1}^K N_k \sum_{C(i)=k}\|x_i - \bar{x}_k\|^2 \\ N_k =& \sum_{i=1}^N I(C(i)=k) \end{align} 这一步很妙,引入了 mean vector $\bar{x}_k$ 后,复杂度就少了一个求和,比起直接用 $d(x_i,x_{i'})$,算法复杂度少乘了一个 $N$。
K-medoids 算法,属于 K-means 的演化版本,放弃了上述“很妙的一步”。根本上,"K-means" 计算得到一个 Cluster 中心,而 “K-medoids”选择一个数据点为中心。前者计算速度快,后者不容易被某些 outlier 误导。算法也是分两步走,先找中心,再重新分类,然后递归至收敛。
K-means 或者 K-medoids 较难确定 K。因为 K 越大,损失函数越小,所以不能用 cross-validation 确定 K。
Hierarchical Clustering 层次聚类,分为自下而上 Agglomerative clustering 和 自上而下 Divisive Clustering 两种。
其中,Agglomerative clustering 分为:
Divisive clustering 为 从 G 中选择平均相似距离最远的点,划分到 H 中: $\bar{d}_G = \frac{1}{N_G} \sum_{i \ in G} \sum_{i'\in H} d_{ii'}$
\begin{align} f(\lambda) = \mu + \mathbf{V}_q \lambda \end{align} 其中 $\mathbf{V}_q$ 为一个 $p\times q$ 的矩阵且所有 q 列都正交, $\lambda$ 是 q 维向量。这两个参数的选择满足近似误差最小,即 \begin{align} \min_{\mu,\{\lambda_i\},\mathbf{V}_q} \sum_{i=1}^N \| x_i - f(\lambda_i)\|^2 \end{align} 对于给定的正交矩阵 $\mathbf{V}_q$,上述求解得到 \begin{align} \hat{\mu} =& \bar{x} \\ \hat{\lambda}_i = & \mathbf{V}_q^T (x_i - \bar{x}) \end{align} 不失一般性,我们会假设 $\hat{\mu} =\bar{x} =0$,或者定义 $\tilde{x}_i = x_i - \bar{x}$,上述最优化问题可以转化为 \begin{align} \min_{\mathbf{V}_q} \sum_{i=1}^N \| x_i - \mathbf{V}_q\mathbf{V}_q^Tx_i\|^2 \end{align} - 其中 $\mathbf{V}_q\mathbf{V}_q^T$ 是一个 映射矩阵,先将 $x_i$ 映射到 q 维度 $\mathbf{V}_q^Tx_i$ ,然后再映射回 p 维度 $\mathbf{V}_q\mathbf{V}_q^Tx_i$。信息损失了 $p-q$ 维。 - 求解时需要将 $N \times p$ 的矩阵 $\mathbf{X}$ 做 SVD 分解,singular value decomposition,$\mathbf{X} = \mathbf{U}\mathbf{D}\mathbf{V}^T$,得到 - $\mathbf{V}_q$ 为 $\mathbf{V}_q$ 前 q 个最大 eigenvalue 对应的列。 - $\hat{\lambda}_i = \mathbf{U}_q\mathbf{D}_q$ 为 $\mathbf{U}\mathbf{D}$ 的前 q 列。事实上,$\mathbf{U}\mathbf{D}$ 的列称为 $\mathbf{X}$ 的主成分 principal components, PCA 由此而来。
Kernel Principal Components。 PCA 对应的是线性的降维,如果数据不是线性的,比如好几个同心环,那么就需要对数据进行预处理,先使用核函数 $\Theta (\cdot)$.
Non-negative Matrix Factorization 与 PCA 类似,将 $N \times p$ 的变量矩阵降维到 $r$,$\mathbf{X} \approx \mathbf{W}\mathbf{H}$,只是这里的矩阵都是 non-negative 的。
Independent Component Analysis, ICA. $\mathbf{X} =\mathbf{U}\mathbf{D}\mathbf{V}^T = \sqrt{N}\mathbf{U} \cdot \mathbf{D}\mathbf{V}^T/\sqrt{N} = \mathbf{S} \mathbf{A}^T $。 ICA 最小化 components 之间的 mutual information: $I(Y) = \sum_{j=1}^p H(Y_j) - H(Y)$