无监督学习 Unsupervised Learning(聚类、矩阵分解、话题模型)

聚类

K-means

输入:数据D={x1,x2,...,xn},簇数目K
1. 随机选取K个种子数据点(seeds)作为K个簇中心
2. repeat
3. foreach x in D do
4. 计算x与每一个簇中心的距离
5. 将x指配到距离最近的簇中心
6. endfor
7. 用当前的簇内点重新计算K个簇中心位置
8. until(达到终止条件)

优点: * 简单:易于理解和实现 * 高效:时间复杂度为O(TKN),其中T为运行轮数,K为簇数目,N为样本数

缺点: * 局部最优解:每一个数据点贪心选择距离最近的中心,不同初始中心可能得到不同的族 * 平均值点一般来说要求为数值型,对于类别型特种不适应 * 用户指定K,提前难以预知 * 离群点敏感(可能为数据准备,预处理过程中出现的错误)


矩阵分解

SVD分解

\[ D = \sum_{k=1}^p\sigma_k\mu_kv_k^T=U {\tiny \sum} V^T \]

\({\tiny \sum}=\begin{bmatrix} \sigma_1 & 0 & 0 & 0\\ 0 & \sigma_2 & 0 & 0\\ 0 & 0 & ... & 0\\ 0 & 0 & 0 & \sigma_n \end{bmatrix}\) 对角矩阵,表示的是特征值,此维度上的方差与能量。

\(u_k,v_k\)表示的是对于\(\sigma_k\)对应的特征向量。 \(U^TU=I,V^TV=I:U,V\)均为正交矩阵。

左特征向量\(U\),每一列对应一个方向,不同的列对应的向量互相垂直,那么将\({\tiny \sum}\)中的\(\sigma_k\)按照从小到大排序,\(u_k,v_k\)也相应排序,可以得到\(u_1\)是对应方差能量最大的方向,\(u_2\)是与\(u_1\)垂直的方差最大的方向... 右特征向量\(V\),由于\(D^T=V{\tiny \sum}U^T\),可以按照与上述相同的理解,因此只是维度存在的不同。

SVD分解与主成分分析(PCA)

给定矩阵 \[ \begin{aligned} S_{M*M}&=D*D^T\\ &=(U {\tiny \sum} V^T)(U {\tiny \sum} V^T)^T\\ &={\tiny \sum}^2 \end{aligned} \] 也就是说\(U\)中对应最大的向量位主成分


LSI分解

NMF分解


单词的分布式表达

每一个词用一般的向量表示 科学院:[1.0,0.5,0],中科院:[0.5,1.0,0],数据挖掘:[0,0.1,1.0] 分布式假设: * Syntagmatic:两个单词频繁在文档中共现,则它们具有一定的语义相似度 * Paradigmatic:两个单词频繁在文档的上下文中共现,则它们具有一定的语义相似度

核心思想:一个单词的表达可以通过在它周围出现的单词计算出来(Word2Vec) 举例如下: d1: Albert Einstein was a physicist d2: Richard Feynman was a physicist

WordsVec 分解Word-Word矩阵,建模单词间的上下文共现

Einstein Feynman physicist
Einstein 0 0 1
Feynman 0 0 1
physicist 1 1 0