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

概述想象下面的问题： >您有一个包含约20,000个文本的数据库，名为“articles” >您想使用聚类算法连接相关的一起，以便一起显示相关的文章 >算法应该做平面聚类(不是分层的) >相关文章应插入表格“相关” >聚类算法应根据文本决定两条或多条文章是否相关 >我想在PHP中编码，但使用伪代码或其他编程语言的代码也可以 我用一个函数check()编写了一个第一个草稿，如果两个输入文章是相关的，那么 想象下面的问题：

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

我用一个函数check()编写了一个第一个草稿，如果两个输入文章是相关的，那么这个“true”就是“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 [only check()]

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

我也想说，我知道有很多算法用于聚类，但是在每个站点上只有数学描述对我来说有点难以理解。所以(伪)代码中的编码示例会很好。

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

解决方法 我所知道的最标准的方式是像你这样的文本数据，就是使用“一袋”的技巧。

首先，为每篇文章创建一个“直方图”。让所有的文章说，你们之间只有500个独特的词。那么这个直方图将是一个大小为500的向量(Array，List，Whatever)，其中数据是每个单词在文章中出现的次数。因此，如果矢量中的第一个位置代表“询问”一词，并且该文章中出现5次，则矢量[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使得这更容易)

这是基本的想法。注意阈值是半任意的;你可能想要找到一个很好的方式来标准化直方图的点积(这几乎需要考虑文章长度)，并决定你认为“相关”。

此外，您不应该将每个单词都放入直方图中。一般来说，你想包括半经常使用的那些：不是在每篇文章中，也不是在一篇文章中。这可以节省您的直方图上的一些开销，并增加您的关系的价值。

顺便说一句，这个技术更详细地描述了here

总结

以上是内存溢出为你收集整理的最佳聚类算法？ (简单解释)全部内容，希望文章能够帮你解决最佳聚类算法？ (简单解释)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。