最好的聚类算法？(简单解释)

Question

想象一下以下问题:

• 你有一个数据库,在一个名为"文章"的表中包含大约20,000个文本
• 您希望使用聚类算法连接相关的文件,以便一起显示相关文章
• 算法应该做平面聚类(不是分层)
• 相关文章应插入表"相关"
• 聚类算法应根据文本决定两篇或多篇文章是否相关
• 我想用PHP编写代码,但伪代码或其他编程语言的例子也可以

我用函数检查()编写了第一个草稿,如果两个输入文章是相关的则给出"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;
    }
}
?>

我还想说,我知道有很多聚类算法,但在每个站点上只有数学描述对我来说有点难以理解.因此(伪)代码中的编码示例会很棒.

我希望你能帮助我.提前致谢!

Answer 1

我所知道的最常用的文本数据方法就是使用'bag of words'技术.

首先,为每篇文章创建单词的"直方图".让我们说你的所有文章之间,你只有500个独特的单词.然后该直方图将是大小为500的向量(Array,List,Whatever),其中数据是每个单词在文章中出现的次数.因此,如果向量中的第一个点代表单词'ask',并且该单词在文章中出现了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会让这更容易)

这是基本的想法.注意,阈值是半任意的; 你可能想找到一个很好的方法来规范你的直方图的点积(这几乎必须考虑文章的长度),并决定你认为'相关'.

此外,您不应该只是将每个单词都放入直方图中.一般来说,您希望包括半频繁使用的那些:不是在每篇文章中,也不是仅在一篇文章中.这可以节省您的直方图上的一些开销,并增加您的关系的价值.

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

Answer 2

也许聚类是错误的策略？

如果你想显示类似的文章,使用相似性搜索代替.

对于文本文章,这是很好理解的.只需将文章插入Lucene等文本搜索数据库,并将当前文章用作搜索查询.在Lucene中,存在一个被称为MoreLikeThis执行此操作的查询:查找类似的文章.

群集是错误的工具,因为(特别是根据您的要求),每篇文章都必须放入某个群集中; 并且相关项对于集群中的每个对象都是相同的.如果数据库中存在异常值 - 很可能是这种情况 - 它们可能会破坏您的群集.此外,集群可能非常大.没有大小限制,聚类算法可能决定将一半的数据集放入同一个集群中.因此,您的数据库中的每篇文章都有10000篇相关文章.通过相似性搜索,您可以获得每个文档的前10个类似项目!

最后但同样重要的是:忘记PHP进行群集.它不是为此而设计的,并且不够高效.但你可以很好地从PHP访问lucene索引.