19

想象以下问题：

  • 您有一个包含大约 20,000 条文本的数据库，表中名为“articles”
  • 您想使用聚类算法连接相关文章，以便一起显示相关文章
  • 该算法应该进行平面聚类（不是分层的）
  • 相关文章应插入“相关”表中
  • 聚类算法应根据文本判断两篇或多篇文章是否相关
  • 我想用 PHP 编写代码，但使用伪代码或其他编程语言的示例也可以

我用函数 check() 编写了初稿，如果两个输入文章相关，则给出“true”，否则给出“false”。其余的代码（从数据库中选择文章，选择要比较的文章，插入相关的文章）也是完整的。也许您也可以改进其余部分。但对我来说重要的要点是函数 check()。因此，如果您可以发布一些改进或完全不同的方法，那就太好了。

方法 1

<?php
$zeit = time();
function check($str1, $str2){
    $minprozent = 60;
    similar_text($str1, $str2, $prozent);
    $prozent = sprintf("%01.2f", $prozent);
    if ($prozent > $minprozent) {
        return TRUE;
    }
    else {
        return FALSE;
    }
}
$sql1 = "SELECT id, text FROM articles ORDER BY RAND() LIMIT 0, 20";
$sql2 = mysql_query($sql1);
while ($sql3 = mysql_fetch_assoc($sql2)) {
    $rel1 = "SELECT id, text, MATCH (text) AGAINST ('".$sql3['text']."') AS score FROM articles WHERE MATCH (text) AGAINST ('".$sql3['text']."') AND id NOT LIKE ".$sql3['id']." LIMIT 0, 20";
    $rel2 = mysql_query($rel1);
    $rel2a = mysql_num_rows($rel2);
    if ($rel2a > 0) {
        while ($rel3 = mysql_fetch_assoc($rel2)) {
            if (check($sql3['text'], $rel3['text']) == TRUE) {
                $id_a = $sql3['id'];
                $id_b = $rel3['id'];
                $rein1 = "INSERT INTO related (article1, article2) VALUES ('".$id_a."', '".$id_b."')";
                $rein2 = mysql_query($rein1);
                $rein3 = "INSERT INTO related (article1, article2) VALUES ('".$id_b."', '".$id_a."')";
                $rein4 = mysql_query($rein3);
            }
        }
    }
}
?>

方法 2 [仅检查（）]

<?php
function square($number) {
    $square = pow($number, 2);
    return $square;
}
function check($text1, $text2) {
    $words_sub = text_splitter($text2); // splits the text into single words
    $words = text_splitter($text1); // splits the text into single words
    // document 1 start
    $document1 = array();
    foreach ($words as $word) {
        if (in_array($word, $words)) {
            if (isset($document1[$word])) { $document1[$word]++; } else { $document1[$word] = 1; }
        }
    }
    $rating1 = 0;
    foreach ($document1 as $temp) {
        $rating1 = $rating1+square($temp);
    }
    $rating1 = sqrt($rating1);
    // document 1 end
    // document 2 start
    $document2 = array();
    foreach ($words_sub as $word_sub) {
        if (in_array($word_sub, $words)) {
            if (isset($document2[$word_sub])) { $document2[$word_sub]++; } else { $document2[$word_sub] = 1; }
        }
    }
    $rating2 = 0;
    foreach ($document2 as $temp) {
        $rating2 = $rating2+square($temp);
    }
    $rating2 = sqrt($rating2);
    // document 2 end
    $skalarprodukt = 0;
    for ($m=0; $m<count($words)-1; $m++) {
        $skalarprodukt = $skalarprodukt+(array_shift($document1)*array_shift($document2));
    }
    if (($rating1*$rating2) == 0) { continue; }
    $kosinusmass = $skalarprodukt/($rating1*$rating2);
    if ($kosinusmass < 0.7) {
        return FALSE;
    }
    else {
        return TRUE;
    }
}
?>

我还想说，我知道有很多聚类算法，但是在每个站点上只有数学描述，这对我来说有点难以理解。所以（伪）代码中的编码示例会很棒。

我希望你能帮助我。提前致谢！

4

4 回答 4

15

我所知道的对文本数据执行此操作的最标准方法是使用“词袋”技术。

首先，为每篇文章创建一个单词的“直方图”。假设在所有文章之间，它们之间只有 500 个唯一词。那么这个直方图将是一个大小为 500 的向量（数组，列表，随便），其中数据是每个单词在文章中出现的次数。因此，如果向量中的第一个点代表单词“asked”，并且该单词在文章中出现 5 次，则 vector[0] 将是 5：

for word in article.text
    article.histogram[indexLookup[word]]++

现在，要比较任何两篇文章，这非常简单。我们简单地将两个向量相乘：

def check(articleA, articleB)
    rtn = 0
    for a,b in zip(articleA.histogram, articleB.histogram)
        rtn += a*b
    return rtn > threshold

（很抱歉使用 python 而不是 PHP，我的 PHP 生锈了，使用 zip 更容易）

这是基本思想。注意阈值是半任意的；您可能希望找到一种对直方图的点积进行归一化的好方法（这几乎必须在某处考虑文章长度）并决定您认为“相关”的内容。

此外，您不应该只将每个单词都放入直方图中。一般来说，您会希望包含那些使用频率不高的那些：不是在每篇文章中，也不是在只有一篇文章中。这为您节省了一些直方图开销，并增加了关系的价值。

顺便说一下，这里更详细地描述了这种技术

于 2009-05-12T15:29:55.097 回答
6

也许集群在这里是错误的策略？

如果要显示相似的文章，请改用相似度搜索。

对于文本文章，这是很好理解的。只需将您的文章插入 Lucene 等文本搜索数据库，然后使用您当前的文章作为搜索查询。在 Lucene 中，有一个名为的查询MoreLikeThis正是执行此操作：查找相似文章。

集群是错误的工具，因为（特别是根据您的要求），每篇文章都必须放入某个集群；并且集群中的每个对象的相关项目都是相同的。如果数据库中存在异常值（很可能是这种情况），它们可能会破坏您的聚类。此外，集群可能非常大。没有大小限制，聚类算法可能会决定将一半的数据集放入同一个聚类中。因此，您的数据库中的每篇文章都有 10000 篇相关文章。使用相似度搜索，您只需获取每个文档的前 10 个相似项！

最后但同样重要的是：忘记使用 PHP 进行集群。它不是为此而设计的，性能也不够好。但是您可能可以很好地从 PHP 访问 lucene 索引。

于 2015-05-02T10:42:27.027 回答
1

我相信您需要对集群做出一些设计决策，并从那里继续：

  1. 为什么要对文本进行聚类？是否要一起显示相关文档？您想通过集群探索您的文档语料库吗？
  2. 因此，您想要平面聚类还是层次聚类？
  3. 现在我们有两个维度的复杂性问题：首先，您从文本中创建的特征的数量和类型 - 单个单词可能数以万计。你可能想尝试一些特征选择——比如在忽略停用词后取 N 个信息量最大的词，或者出现次数最多的 N 个词。
  4. 其次，您希望最大限度地减少测量文档之间相似性的次数。正如 bubaker 正确指出的那样，检查所有文档对之间的相似性可能太多了。如果聚类成少量的簇就足够了，你可以考虑K-means clustering，它基本上是：选择一个初始的 K 个文档作为簇中心，将每个文档分配到最近的簇，通过查找文档向量均值重新计算簇中心，以及迭代。每次迭代只需花费 K* 数量的文档。我相信还有一些启发式方法可以减少层次聚类所需的计算数量。
于 2009-05-13T08:17:22.177 回答
0

similar_text方法 #1 中调用的函数是什么样的？我认为您所指的不是聚类，而是相似性度量。我无法真正改进 White Walloun 的 :-) 直方图方法——这是一个值得阅读的有趣问题。

无论您如何实现check()，您都必须使用它进行至少 200M 的比较（一半20000^2）。“相关”文章的截断可能会限制您在数据库中存储的内容，但似乎过于随意而无法捕捉所有有用的文本聚类，

我的方法是修改check()以返回“相似性”指标（$prozent或rtn）。将20K x 20K矩阵写入文件并使用外部程序执行聚类以识别每篇文章的最近邻居，您可以将其加载到related表中。我会在其中进行聚类R- 有一个很好的教程，用于在R从php.

于 2009-05-12T17:26:47.513 回答