9

这是一个家庭作业问题。我有一个巨大的文件，里面全是文字。我的挑战是将这些词分类为充分代表这些词的不同组/集群。我处理它的策略是使用 K-Means 算法，如您所知，它采用以下步骤。

  1. 为整个组生成 k 个随机均值
  2. 通过将每个单词与最接近的平均值相关联来创建 K 个集群
  3. 计算每个集群的质心，成为新的均值
  4. 重复步骤 2 和步骤 3，直到达到某个基准/收敛。

理论上，我有点明白，但不完全明白。我认为在每一步，我都有与之相对应的问题，这些是：

  1. 我如何决定 k 随机均值，从技术上讲，我可以说 5，但这不一定是一个好的随机数。那么这个 k 纯粹是一个随机数还是它实际上是由启发式驱动的，例如数据集的大小、所涉及的单词数等

  2. 你如何将每个单词与最接近的意思联系起来？从理论上讲，我可以得出结论，每个单词都通过其与最近均值的距离相关联，因此如果有 3 个均值，则属于特定聚类的任何单词都取决于它与哪个均值的距离最短。但是，这实际上是如何计算的？在两个单词“group”、“textword”之间并假设一个平均单词“pencil”，我如何创建一个相似度矩阵。

  3. 你如何计算质心？

  4. 当您重复第 2 步和第 3 步时，您是否假设每个先前的集群都是一个新的数据集？

很多问题，我显然不清楚。如果有任何我可以阅读的资源，那就太好了。维基百科还不够:(

4

3 回答 3

12

由于您不知道确切的集群数量 - 我建议您使用一种层次聚类：

  1. 想象一下，你所有的词都只是非欧几里得空间中的一个点。使用Levenshtein 距离来计算单词之间的距离（如果您想检测词典上相似的单词集群，它的效果很好）
  2. 构建包含所有单词的最小生成树
  3. 删除长度大于某个阈值的链接
  4. 链接的词组是相似词的集群

这是一个小插图：

在此处输入图像描述

PS你可以在网上找到很多论文，其中描述了基于构建最小生成树的聚类

PPS如果要检测语义相似词的聚类，则需要一些自动词库构建的算法

于 2012-12-08T12:06:28.493 回答
0

关于距离：其实Levenshtein（或编辑）距离满足三角不等式。它还满足成为度量的其余必要属性（并非所有距离函数都是度量函数）。因此，您可以使用此度量函数实现聚类算法，这是您可以用来计算相似度矩阵 S 的函数：

-> S_{i,j} = d(x_i, x_j) = S_{j,i} = d(x_j, x_i)

值得一提的是，Damerau-Levenshtein 距离不满足三角不等式，所以要小心。

关于 k-means 算法：是的，在基本版本中，您必须手动定义 K 参数。对于给定的度量，算法的其余部分是相同的。

于 2014-07-01T19:32:59.380 回答
0

您必须为 k-means 选择“k”是 k-means 的最大缺点之一。但是，如果您使用此处的搜索功能，您会发现许多问题涉及选择 k 的已知启发式方法。主要是通过比较多次运行算法的结果。

至于“最近”。K-means 实际上不使用距离。有些人认为它使用欧几里得，其他人说它是平方欧几里得。从技术上讲，k-means 感兴趣的是方差。它通过将每个对象分配给集群以使方差最小化，从而最小化整体方差。巧合的是，平方偏差的总和 - 一个对象对总方差的贡献 - 在所有维度上正是平方欧几里德距离的定义。由于平方根是单调的，你也可以使用欧几里得距离。

无论如何，如果您想对单词使用 k-means，您首先需要将单词表示为平方欧几里得距离有意义的向量。我认为这并不容易，甚至不可能。

于 2012-12-08T09:32:44.937 回答