最好的聚类算法?(简单解释一下)
-
21-08-2019 - |
题
想象一下以下问题:
- 您有一个名为“文章”的表,其中包含大约 20,000 条文本的数据库
- 您希望使用聚类算法连接相关文章,以便将相关文章显示在一起
- 该算法应该进行平面聚类(而不是分层聚类)
- 相关文章应插入“相关”表中
- 聚类算法应该根据文本来决定两篇或多篇文章是否相关
- 我想用 PHP 编写代码,但使用伪代码或其他编程语言的示例也可以
我用函数 check() 编写了初稿,如果两个输入文章相关,则给出“true”,如果不相关,则给出“false”。其余代码(从数据库中选择文章、选择要比较的文章、插入相关文章)也已完成。也许你也可以改善其余的事情。但对我来说重要的要点是函数 check()。因此,如果您可以发布一些改进或完全不同的方法,那就太好了。
方法一
<?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;
}
}
?>
我还想说,我知道有很多聚类算法,但每个站点上只有数学描述,这对我来说有点难以理解。因此,用(伪)代码编写示例会很棒。
我希望你可以帮助我。提前致谢!
解决方案
据我所知,对文本数据执行此操作的最标准方法是使用“词袋”技术。
首先,为每篇文章创建一个单词“直方图”。假设您的所有文章之间只有 500 个独特的单词。那么这个直方图将是一个大小为 500 的向量(Array、List、Whatever),其中数据是每个单词在文章中出现的次数。因此,如果向量中的第一个点代表单词“asked”,并且该单词在文章中出现了 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 使这变得更容易)
这是基本思想。注意阈值是半任意的;您可能想要找到一种好方法来规范化直方图的点积(这几乎必须在某处考虑文章长度)并决定您认为“相关”的内容。
另外,您不应该只将每个单词都放入直方图中。一般来说,您会希望包含那些不经常使用的内容:不是在每一篇文章中,也不是仅在一篇文章中。这可以节省您的直方图的一些开销,并增加关系的价值。
顺便说一下,这个技术有更详细的描述 这里
其他提示
或许 集群是错误的策略 这里?
如果你想显示 相似的 文章, 使用 相似性搜索 反而.
对于文本文章来说,这是很好理解的。只需将您的文章插入到 Lucene 等文本搜索数据库中,然后使用您当前的文章作为搜索查询即可。在Lucene中,存在一个 查询称为 MoreLikeThis
其执行的正是这样的:查找类似的文章。
集群是错误的工具,因为(特别是根据您的要求), 每一个 文章必须放入某个簇中;并且集群中每个对象的相关项都是相同的。如果数据库中存在异常值(很可能是这种情况),它们可能会破坏您的聚类。此外, 集群可能非常大. 。没有大小限制,聚类算法可能决定将一半的数据集放入同一个聚类中。因此,数据库中的每篇文章都有 10000 篇相关文章。通过相似度搜索,您只需获取每个文档的前 10 个相似项即可!
最后但并非最不重要的:忘记用于集群的 PHP。它不是为此而设计的,而且性能也不够。但是您可能可以很好地从 PHP 访问 lucene 索引。
我相信您需要做出一些有关集群的设计决策,并从那里继续:
- 为什么要对文本进行聚类?您想将相关文档一起显示吗?您想通过集群探索您的文档语料库吗?
- 结果,你想要 平坦的 或者 等级制度 聚类?
- 现在我们有两个维度的复杂性问题:首先,您从文本中创建的特征的数量和类型 - 单个单词的数量可能有数万个。你可能想尝试一些 特征选择 - 比如取信息量最大的N个单词,或者出现次数最多的N个单词,忽略后 停用词.
- 其次,您希望最大限度地减少测量文档之间相似性的次数。正如布巴克正确指出的那样,检查所有文档对之间的相似性可能太过分了。如果聚类成少量簇就足够了,您可以考虑 K-均值聚类, ,这基本上是:选择初始 K 个文档作为聚类中心,将每个文档分配到最近的聚类,通过查找文档向量均值重新计算聚类中心,然后迭代。每次迭代仅花费 K* 文档数。我相信也有一些启发式方法可以减少层次聚类所需的计算数量。
什么是 similar_text
方法 #1 中调用的函数是什么样的?我认为你指的不是聚类,而是相似性度量。我无法真正改进 White Walloun 的 :-) 直方图方法 - 这是一个值得阅读的有趣问题。
然而你实现 check()
, ,你必须使用它进行至少 200M 的比较(一半 20000^2
)。“相关”文章的截止可能会限制您在数据库中存储的内容,但似乎过于武断,无法捕获所有有用的文本聚类,
我的方法是修改 check()
返回“相似性”指标($prozent
或者 rtn
)。写下 20K x 20K
矩阵到文件并使用外部程序执行聚类来识别每篇文章的最近邻居,您可以将其加载到 related
桌子。我会做聚类 R
- 有一个不错的 教程 用于对正在运行的文件中的数据进行聚类 R
从 php
.