1. 实验要求
  2. 实验环境
  3. 实验过程
    1. 对文档分词
    2. 计算TF-IDF
    3. 进行SVD
    4. 进行LSI查询
  4. 参考

针对给定的文档集合，基于潜在语义索引原理（Latent Semantic Indexing, LSI），构建一个简单的搜索算法。

实验要求

  1. 针对给定的文档集合分词，计算每个词的TFIDF，构建文档向量

  2. 利用JAMA包，基于LSI原理，对Term-Document矩阵构造新的矩阵

  3. 基于以下关键词查询，基于LSI原理进行搜索，输出相对应的准确度

  4. 算法要求有相应的注释，输出包括：查询关键词，查询结果，根据LSI矩阵K的不同取值得到的查询准度：（K=10,20,30,40,50,100）

实验环境

操作系统：Windows 10

开发环境：JDK 1.7

Java库: ansj_seg-3.7.1-all-in-one.jar, Jama-1.0.3.jar

实验过程

对文档分词

使用ansj_seg1对文档进行分词。

输入：字符串

输出：一个带词性的单词列表

1
2
3
4
5
import org.ansj.domain.Term;
import org.ansj.splitWord.analysis.ToAnalysis;

// String doc
List<Term> termList = ToAnalysis.parse(doc);

计算TF-IDF

TF-IDF2即term frequency–inverse document frequency。

计算所有文档中所有单词与所有文档之间的TF-IDF值，构成term-by-document matrix。

1
2
3
// pseudo code
tf(term, allTerms) = allTerms.count(term) / allTerms.size()
idf(term, all) = 1 + log(allDocTerms.size() / allDocTerms.count(term))

其中allTerms指某个文档中的所有term，allDocTerms指所有文档中的所有term。

进行SVD

根据潜在语义索引（Latent Semantic Indexing，LSI）3原理，使用Jama4对上面得到的Term-Document矩阵进行奇异值分解（Singular Value Decomposition，SVD）5。

根据SVD公式：

\(A = U \Sigma V^T\)

\(A_k = U_k \Sigma_k V^T_k\)

K作为一个参数会影响结果，这里对K取不同的值进行实验。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import Jama.Matrix;
import Jama.SingularValueDecomposition;

Matrix A;
// A = U S V^T
SingularValueDecomposition svd = A.svd();
// U: concept-by-term matrix
U = svd.getU();
// V: concept-by-document matrix
V = svd.getV();
// S: elements assign weights to concepts
S = svd.getS();
Matrix Uk = U.getMatrix(0, U.getRowDimension() - 1, 0, K - 1);
Matrix Sk = S.getMatrix(0, K - 1, 0, K - 1);
Matrix VkT = V.getMatrix(0, V.getRowDimension() - 1, 0, K - 1).transpose();

进行LSI查询

根据LSI原理，对每个待查询关键词进行分词并构建小文档，并于每个词计算TF-IDF得到一个向量。

根据 https://en.wikipedia.org/wiki/Latent_semantic_indexing 知，\(V = A^T U S^{-1}\)

故可对上述得到的向量进行转换，并与1000个文档进行余弦相似性计算，得到相似性向量。

把相似性向量从大到小进行排序即为相应的搜索结果。也可以对每个查询词的相似性向量保存到csv中，可进行后续的分析。

1
2
3
4
5
6
7
8
// Q^T U S^{-1}
Matrix Qk = Q.times(Uk.times(Sk.inverse()));
for (int i = 0; i < VkT.getColumnDimension(); ++i) {
    Matrix doc = VkT.getMatrix(0, VkT.getRowDimension() - 1, i, i);
    double cosineSimilarity = Qk.times(doc).getArray()[0][0]
            / (Qk.norm2() * doc.norm2());
    similarityList.add(cosineSimilarity);
}

参考

  1. AnsjSeg 使用手册. http://nlpchina.github.io/ansj_seg/↩︎

  2. tf–idf. 维基百科. 最后修订于2016年3月8日. https://en.wikipedia.org/wiki/Tf%E2%80%93idf↩︎

  3. Latent semantic indexing. 维基百科. 最后修订于2016年2月11日. https://en.wikipedia.org/wiki/Latent_semantic_indexing↩︎

  4. JAMA : A Java Matrix Package. National Institute of Standards and Technology. 最后修订于2012年11月23日. http://math.nist.gov/javanumerics/jama/↩︎

  5. Singular value decomposition. 维基百科. 最后修订于2016年3月22日. https://en.wikipedia.org/wiki/Singular_value_decomposition↩︎