最佳聚类算法是什么？（简单解释）

Question

最佳聚类算法是什么？（简单解释）

algorithmtextcluster-analysisdata-miningtext-mining

19

假设你面临以下问题：

你有一个名为“articles”的表格，其中包含约20,000个文本
你想使用聚类算法将相关的文章连接起来，以便将相关文章一起展示
该算法应该进行平面聚类（不是分层聚类）
相关文章应被插入到名为“related”的表格中
聚类算法应根据文本决定两个或多个文章是否相关
我希望使用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);
            }
        }
    }
}
?>

第二种方法 [仅使用check()]

<?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;
    }
}
?>

我想说的是，我知道有很多聚类算法，但在每个网站上都只有数学描述，对我来说有点难以理解。因此，提供（伪）代码的编码示例将是很好的帮助。

我希望你能帮助我。先谢谢了！

- caw

1

有WordPress插件（是的，我知道，不必提醒）可以出人意料地做得很好，实际上它们执行合理的聚类（通常使用TF-IDF和k-means之类的单词背景），你可以参考它们获得灵感（其中一些是MIT开源的）。 - Benjamin Gruenbaum

2

我认为Anony-Mousse是正确的：聚类不是这里的理想工具。如果每个文档只属于一个簇，则会出现边界附近的文档与其他附近簇中的文档比自己所在簇中的大多数文档更相似的问题。 - j_random_hacker

4个回答

6

也许在这里使用聚类是错误的策略？

如果您想显示相似文章，请改用相似性搜索。

对于文本文章，这是很好理解的。只需将文章插入到像Lucene这样的文本搜索数据库中，并使用当前文章作为搜索查询。在Lucene中，存在一个名为MoreLikeThis的查询，可以执行查找相似文章的操作。

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

最后但并非不重要的一点是：不要考虑使用PHP进行集群。它并未为此而设计，且性能不足。但你可能可以从PHP中很好地访问Lucene索引。

- Has QUIT--Anony-Mousse

1

我相信你需要对集群进行一些设计决策，然后从那里继续：

你为什么要对文本进行聚类？是想将相关的文档放在一起展示吗？还是想通过聚类来探索你的文档语料库？
因此，你想要平面聚类还是分层聚类？
现在我们有一个复杂性问题，涉及两个方面：首先，你从文本中创建的特征数量和类型 - 单词可能达到数万个。你可以尝试一些特征选择 - 比如选取最具信息量的N个单词，或者出现次数最多的N个单词，在忽略停用词后。
其次，你希望尽量减少测量文档相似度的次数。正如bubaker所指出的那样，检查所有文档对之间的相似度可能太多了。如果将其聚类成少量的簇已经足够，你可以考虑K均值聚类，它基本上是：选择初始的K个文档作为簇中心，将每个文档分配给最近的簇，通过找到文档向量的平均值重新计算簇中心，并迭代。这只需要每次迭代K*文档数量的成本。我相信对于减少分层聚类所需的计算次数也有一些启发式方法。

- Yuval F

谢谢，好问题！ 1）我想一起显示相关文档。 2）该算法应该执行平面聚类。 3）如果文本很长，这将非常有用，但在我的情况下，文章最多只包含510个字符。所以这并不是真正必要的，对吧？ 4）使用k-means方法听起来不错，但我需要很多聚类，并且新的聚类必须不断地被创建。不过我能用k-means吗？ - caw

您可以使用K-means算法，其中K可以非常大。代价是必须检查每个文档与每个聚类中心的相似性。对我来说，“不断创建新的聚类”听起来像自上而下的分层聚类，但您可以在多个时期内工作-从小的K开始，运行K-means直到收敛，并使用这些聚类。稍后，增加K，重新从头开始运行K-means，并使用生成的聚类等。 - Yuval F

哦，我不知道k-means算法的工作原理。如果它是这样工作的话，我不能使用它，因为我不知道聚类中心的数量。我有一个新闻文章数据库，所有关于同一主题的文章应该被分组。 - caw

0

similar_text 函数在第一种方法中是如何调用的？我认为您所指的并不是聚类，而是相似度度量。我无法真正改进 White Walloun 的直方图方法 - 这是一个有趣的问题，可以进行一些阅读来了解。

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

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

- bubaker

函数similar_text()“计算Oliver [1993]中描述的两个字符串之间的相似度”。是的，你说得对，它更像是一种相似性度量。但是你需要相似性检查来进行聚类，不是吗？ - caw

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Albinofrenchy · Accepted Answer

我所知道的在文本数据上实现此操作最标准的方式是使用“词袋”技术。

首先，为每篇文章创建一个单词的“直方图”。假设在所有文章中，你只有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可以使这一点更容易）

这是基本的想法。请注意，阈值是半随意的；你可能需要找到一种很好的方法来归一化直方图的点积（这几乎必须在文章长度中考虑某些因素），并决定你认为什么是“相关”的。

此外，你不能只把每个单词都放到直方图里。通常，你会希望包括那些被半频繁使用的单词：不是在每篇文章中使用，也不是只在一篇文章中使用。这可以节省直方图开销，并增加你关系的价值。

顺便说一句，这种技术在这里有更详细的描述。