将单词聚类成组

Question

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

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

从理论上讲,我有点得到它,但并不完全.我想在每一步,我都有与之相对应的问题,这些是:

1. 我如何决定k随机方法,技术上我可以说5,但这可能不一定是一个好的随机数.那么这个k纯粹是一个随机数,还是实际上是由启发式驱动的,例如数据集的大小,涉及的单词数量等等

2. 你如何将每个单词与最近的平均值相关联？从理论上讲,我可以得出结论,每个单词的距离与最近的平均值相关联,因此,如果有3个均值,任何属于特定群集的单词都取决于它具有最短距离的平均值.但是,这实际上是如何计算的？在两个单词"group","textword"和假设平均单词"pencil"之间,如何创建相似度矩阵.

3. 你如何计算质心？

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

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

Answer 1

由于您不知道确切的簇数 - 我建议您使用一种层次聚类:

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

这是一个小插图:

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

PPS如果要检测语义相似的单词集群,则需要一些自动叙词表构造算法

Answer 2

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

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

不管怎样，如果你想对单词使用 k 均值，你首先需要将单词表示为向量，其中平方欧氏距离是有意义的。我认为这并不容易，甚至可能不可能。