Spark数据挖掘-基于 LSA 隐层语义分析理解APP描述信息(2) - clebeg的个人空间 - 开源中国
Spark数据挖掘-基于 LSA 隐层语义分析理解APP描述信息(2)
1 前言
Spark 通过调用 RowMatrix 的 computeSVD 方法会得到三个重要的矩阵 U、S、V , 而且:原始矩阵 近似等于 U * S * V
它们含义分别如下:
- V: 每一行表示单词,列表示概念,矩阵的值表示单词在概念里面的重要程度
- U: 每一行表示文档,列表示概念,矩阵的值表示文档在概念里面的重要程度
- S: 对角矩阵,每一个对角线元素代表概念的重要程度
通过这个文档,首先想到的是文档中最重要的概念是什么?概念往往对应话题,这样基本就能确定文档的主题了,然后每个主题通过V矩阵可以得到重要的词,这样就可以给文档添加标签了,但是其实可以走的更远,本文将重点研究如何使用这两个矩阵,这里的用途很容易推广到LDA模型,LDA 模型得到 phi(词与topic关系矩阵) 和 theta(文档与topic的关系矩阵) 两个矩阵之后也可以干这些事。接下来主要尝试回答下面三个问题:
- 文档与文档关系如何?
- 词与词关系如何?
- 词与文档关系如何?
- 给出一系列查询词最相关的文档是哪些?
2 粗浅的解决方案
其实从最原始的词文档矩阵可以得到上面这些问题粗浅的答案:比如词与词的重要程度可以计算词文档矩阵中对应列之间的余弦相似性。余弦相似度计算的是高维文档空间中两个点之间向量的夹角,越相同方向的点认为相似度越高。余弦相似度计算的就是两个向量的点积除以两个向量长度的乘积。通用的计算行之间的余弦距离就得到了文档与文档的相似度。而词与文档的重要程度就对应该矩阵中这两个对象交叉的位置。
然而这些重要性得分都是很粗浅的,因为这些都是来自于对文档中词简单计数统计,根本没有考虑词之间的语义关系等。
3 基于LSA的解决方案
LSA 提供更深入的理解语料库的得分矩阵。基于这些矩阵可以得到更加有深度的结论。例如:一些文件只出现“新闻”,但是不出现“资讯”,而另外一下文章刚好相反,但是它们可能会通过“阅读”这个词联系在一起。
LSA 这种表示的方式从效率的角度来看也更有优势。LSA 将重要的信息压缩到低维空间来代替原始的词文档矩阵。这样使得很多计算更加快。因为计算原始词文档矩阵中词与其他词的重要程度需要的时间复杂度正比于单词的数量乘以文档的数量。LSA 可以通过将概念空间表示映射到词空间达到通用的效果,时间复杂度正比于单词的数量乘以概念的个数 K。数据之间的相关性通过这种低秩近似重新编码从而使得不需要访问整个语料库。
4 词-词相关性
LSA 是如何理解词与词之间的距离的呢?其实通过将 SVD 奇异值分解得到的三个矩阵相乘就会得到原始矩阵的一个近似,那么这个近似矩阵列之间的余弦距离就是原始的词距离的一个近似,只不过现在有下面的三点优化:
- 同义词变为同一个词
- 降低一词多义词的权重
- 去掉一些噪音
这样就会使得词之间的距离更加合理。幸运的是不需要重新将三个因子矩阵相乘再去计算词之间的相似性,线性代数已经证明:相乘之后的矩阵列与列之间的余弦就等于
St(V):(t 表示转置)这个矩阵对应列之间的余弦。
考虑给定一个词计算最相关的特定词这个任务:由于S是对角矩阵,那么S的转置就等于S,那么S*t(V)的列就变为了VS的行。通过对VS的每一行长度归一化,然后将VS乘以给定词对应的列转变的列向量就得到了这个词与每个词之间的余弦。具体代码如下:
import breeze.linalg.{DenseVector => BDenseVector}
import breeze.linalg.{DenseMatrix => BDenseMatrix}
def topTermsForTerm(
normalizedVS: BDenseMatrix[Double],
termId: Int): Seq[(Double, Int)] = {
//得到termId对应的行
val rowVec = new BDenseVector[Double](
row(normalizedVS, termId).toArray)
//将VS归一化的矩阵乘上面对应的行,得到该term与每个单词的余弦距离
val termScores = (normalizedVS * rowVec).toArray.zipWithIndex
termScores.sortBy(-_._1).take(10)
}
//计算 VS
val VS = multiplyByDiagonalMatrix(svd.V, svd.s)
//将 VS 的行归一化
val normalizedVS = rowsNormalized(VS)
def printRelevantTerms(term: String) {
val id = idTerms(term)
printIdWeights(topTermsForTerm(normalizedVS, id, termIds)
}
利用上面的代码查询了和“银行”相关的词,结果如下:
银行:1.0000000000000007
农商:0.5731472845623417
浦发:0.5582996267582955
灵犀:0.5546113928156614
乌海:0.5181220508630512
邮政:0.49403542009285284
花旗:0.4767076670441433
渣打:0.4646580481689233
通畅:0.46282711600593196
缝隙:0.4500830196782121
语料库不足是导致效果一般的最大问题。
5 文档-文档相关性
文档与文档的相关性与词与词之间的相关性思路完全一样,只不过这次用的矩阵是U,U是分布式存储的,所以代码有点不同:
import org.apache.spark.mllib.linalg.Matrices
def topDocsForDoc(normalizedUS: RowMatrix, docId: Long)
: Seq[(Double, Long)] = {
val docRowArr = row(normalizedUS, docId)
val docRowVec = Matrices.dense(docRowArr.length, 1, docRowArr)
val docScores = normalizedUS.multiply(docRowVec)
val allDocWeights = docScores.rows.map(_.toArray(0)).
zipWithUniqueId()
allDocWeights.filter(!_._1.isNaN).top(10)
}
val US = multiplyByDiagonalMatrix(svd.U, svd.s)
val normalizedUS = rowsNormalized(US)
def printRelevantDocs(doc: String) {
val id = idDocs(doc)
printIdWeights(topDocsForDoc(normalizedUS, id, docIds)
}
6 词-文档之间的相关性
同样的道理,词文档之间的相关性也是通过 USV 这个矩阵中的每个位置的元素去近似的,比如词 t 与文档 d 的关系就是: U(d) * S * V(t),根据线性代数的基本理论,可以很容易得到词 t 与所有文档的关系为:U * S * V(t) 或者文档 d 与所有词的关系为:U(d) * S * V。这样就很容易知道与某个文档最相关的前几个词,以及与某个词最相关的文档。具体的应用代码如下:
def topDocsForTerm(US: RowMatrix, V: Matrix, termId: Int)
: Seq[(Double, Long)] = {
//得到词对应的行
val rowArr = row(V, termId).toArray
//将改行转为列向量
val rowVec = Matrices.dense(termRowArr.length, 1, termRowArr)
//计算 US 乘以列向量
val docScores = US.multiply(termRowVec)
//得到所有文档与词之间的关系的得分
val allDocWeights = docScores.rows.map(_.toArray(0)).zipWithUniqueId()
//选择最重要的10篇文档
allDocWeights.top(10)
}
//打印结果
def printRelevantDocs(term: String) {
val id = idTerms(term)
printIdWeights(topDocsForTerm(normalizedUS, svd.V, id, docIds)
}
7 查询多个词相关的文档
查询一个词,相当于上面的词与文档的关系,其实就是将 V 转置之后乘以一个长度为词向量长而且只有一个元素为 1 的列向量,值为 1 的位置对应的就是该词的位置,而多个词,那么就通过乘以一个长度为词向量长而且对应查询词位置都是该词的idf权重其他位置为0的列向量即可。具体代码如下:
import breeze.linalg.{SparseVector => BSparseVector}
//得到查询词对应位置为idf权重,其他位置为0的向量
def termsToQueryVector(
terms: Seq[String],
idTerms: Map[String, Int],
idfs: Map[String, Double]): BSparseVector[Double] = {
//先得到查询词在整个词向量的下标索引位置
val indices = terms.map(idTerms(_)).toArray
//将对应位置的idf权重找出来
val values = terms.map(idfs(_)).toArray
//转为向量 长度为词向量长度,很多位置的值为零,查询词位置值为 idf 权重
new BSparseVector[Double](indices, values, idTerms.size)
}
//得到 US*t(t(V)*上面方法得到的向量)
def topDocsForTermQuery(
US: RowMatrix,
V: Matrix,
query: BSparseVector[Double]): Seq[(Double, Long)] = {
val breezeV = new BDenseMatrix[Double](V.numRows, V.numCols,
V.toArray)
//计算 t(V)*上面方法得到的向量
val termRowArr = (breezeV.t * query).toArray
//得到 t(t(V)*上面方法得到的向量)
val termRowVec = Matrices.dense(termRowArr.length, 1, termRowArr)
//计算 US*t(t(V)*上面方法得到的向量)
val docScores = US.multiply(termRowVec)
val allDocWeights = docScores.rows.map(_.toArray(0)).
zipWithUniqueId()
allDocWeights.top(10)
}
def printRelevantDocs(terms: Seq[String]) {
val queryVec = termsToQueryVector(terms, idTerms, idfs)
printIdWeights(topDocsForTermQuery(US, svd.V, queryVec), docIds)
}
8 附录
上面代码中用到一些辅助的方法,因为比较简单就不详细分析,这里简单做一个汇总:
def row(normalizedVS: DenseMatrix[Double], termId: Int) = {
(0 until normalizedVS.cols).map(i => normalizedVS(termId, i))
}
def multiplyByDiagonalMatrix(mat: Matrix, s: Vector) = {
val sArr = s.toArray
new BDenseMatrix[Double](mat.numRows, mat.numCols, mat.toArray)
.mapPairs{case ((r, c), v) => v * sArr(c)}
}
def rowsNormalized(bm: BDenseMatrix[Double]) = {
val newMat = new BDenseMatrix[Double](bm.rows, bm.cols)
for (r <- 0 until bm.rows) {
val len = math.sqrt((0 until bm.cols).map{c => math.pow(bm(r, c), 2)}.sum)
(0 until bm.cols).foreach{c => newMat.update(r, c, bm(r, c)/len)}
}
newMat
}