数据挖掘中可用哪些方法计算相似度

数据挖掘中可用哪些方法计算相似度

两者的定义你说的都对

两者的关系是 矩阵的秩等于矩阵列向量组的秩(即列秩), 而不是等于列数

矩阵的秩 也等于行向量组的秩, 即行秩

计算矩阵的秩: 用初等行变换化为梯矩阵, 非零行数即矩阵的秩

列变换也可用, 但行变换足够

计算向量组的秩: 将向量按列构成矩阵, 用初等行变换化梯矩阵, 非零行数即向量组的秩, 非零行的首非零元所在列对应的向量构成一个极大无关组

如何使用MapReduce计算相似度

由于在索引中的数据结构是倒排索引，其结构如下：

倒排索引（<word doc_i1 doc_i2 doc_ik ...>）

举例如下：

Word occurrence@DocID........

cat 6@Doc1 3@Doc2 4@Doc3... etc

Hot 9@Doc1 2@Doc3 10@Doc5... etc

倒排索引是MapReduce的关键部分。我们需要解决的问题是将两个文档向量（也就是将要进行比较的文档）输入到reducer中。

我们要考虑的是<Doc1, Doc3>的相似性。如何获得他们对应的向量并传给reducer？

相当简单～

Mapper的输出应该是这样的：

Key:<Document_one, Document_two> Value:<occurrence, occurrence>

所以对上面的两个文档，<Doc1, Doc3>对应第一个word cat将是：

Key:<doc1, doc3> Value:<6, 3>

通过这样的方法，在reducer中，你们会有这些值的一个list，对两个文档中出现的word的向量，这就可以在reducer中计算相似度了。

当然，也可以将occurrence改称TF或者TF-IDF向量或者其他什么东西。这里的关键就是要得到正确的KEY-VALUE。

在reducer这儿，你可以获得：

Key: <doc1, doc3> Value: [<6, 4>, <9, 2>]

因此，余弦相似度可以直接通过doc1 (6, 9)和doc3 (4, 2)点乘获得：

(6*4)+(9*2)... etc for larger vectors

分母部分可以这样计算：

sqrt(6^2 + 9^2) * sqrt(4^2 + 2^2) * ...

你可以在reducer中进行这个计算，因为你有两个文档的向量。当然在你的值计算完后，你可以以任何方式从reducer中输出他们