7

我希望根据它们的标签对许多提要进行聚类。一个典型的例子是 twitter 提要。每个提要都有与之关联的用户定义标签。通过分析标签，是否有可能将提要分成不同的组，并告诉这么多提要基于这么多标签。一个例子是 -

  • Feed1 - 印度尼西亚地震#earthquake #asia #bad
  • Feed2 - 我所在地区发生大地震#earthquake #bad
  • Feed3 - 我的父母去了新加坡#asia #tour
  • Feed4 - XYZ 公司正在裁员很多人#XYZ #layoff #bear
  • Feed5 - XYZ 越来越糟糕，正在计划裁员 #XYZ #layoff #bad
  • Feed6 - XYZ 处于裁员狂潮中#layoff #XYZ #worst

聚类后

  • #asia , # 地震 - Feed1 , Feed2
  • #XYZ , # 裁员 - Feed4 , Feed 5 , Feed6

这里的聚类纯粹是基于标签。有没有什么好的算法来实现这一点

4

2 回答 2

7

如果我正确理解您的问题，您希望将标签聚集在一起，然后根据提要中的标签将提要放入这些集群中。

为此，您可以根据标签一起出现的提要数量创建标签之间的相似性度量。对于您的示例，这将是这样的

               #earthquake | #asia | #bad | ...
#earthquake        1       |  1/2  |  2/2
#asia             1/2      |   1   |  1/2
#bad              2/3      |  1/3  |   1
...

在这里，值(i,j)等于frequency of (i,j)/frequency of (i)。

现在您有了标签之间的相似性矩阵，您几乎可以使用任何适合您需求的聚类算法。由于标签的数量可能非常大，并且在运行算法之前估计集群的数量很困难，我建议使用一些层次聚类算法，例如快速模块化聚类，它也非常快（请参阅此处的一些详细信息）。但是，如果您对想要将其分解成的集群数量有一些估计，那么光谱聚类也可能很有用（请参阅此处的一些详细信息）。

After you cluster the tags together, you could use a simple approach to assign each feed to a cluster. This can be very simple, for example, counting the number of tags from each cluster in a feed and assigning a cluster with the maximum number of matching tags.

If you are flexible on your clustering strategy, then you could also try clustering the feeds together in a similar way by creating a similarity between the feeds based on the number of common tags between the feeds and then applying a clustering algorithm on the similarity matrix.

于 2013-02-14T15:40:37.623 回答
2

有趣的问题。我在这里编造东西，但我认为这会奏效。

算法

对于每个提要，提供一个完整的标签组合列表（长度 >= 2），可能为了一致性而排序。例如：

  • Feed1: (asia-bad), (asia-earthquake), (bad-earthquake), (asia-bad-earthquake)
  • Feed2：（严重地震）
  • Feed3：（亚洲巡回演唱会）
  • Feed4: (bear-layoff), (bear-XYZ), (layoff-XYZ), (bear-layoff-XYZ)
  • Feed5: (bad-layoff), (bad-XYZ), (layoff-XYZ), (bad-layoff-XYZ)
  • Feed6: (layoff-worst), (layoff-XYZ), (worst-XYZ), (layoff-worst-XYZ)

然后反转映射：

  • （亚洲坏）：Feed1
  • （亚洲地震）：Feed1
  • （严重地震）：Feed1、Feed2
  • （亚洲严重地震）：Feed1
  • （亚洲巡回演唱会）：Feed3
  • （熊裁员）：Feed4
  • ...
  • （裁员-XYZ）：Feed4、Feed5、Feed6
  • ...

然后，您可以剔除频率高于某个阈值的所有条目。在这种情况下，如果我们将频率阈值设为 2，那么 Feed1 和 Feed2 会得到 (bad-earthquake)，Feed4、Feed5 和 Feed6 会得到 (layoff-XYZ)。

性能问题

一个幼稚的实现将具有极差的性能——每个提要的标签数量呈指数级增长（更不用说空间要求了）。但是，有多种方法可以应用启发式方法来改进这一点。例如：

  1. 通过扫描所有提要（或随机选择 X 个提要）确定最流行的 X 标签——这与每个提要的标签数量成线性关系。然后只考虑每个提要的 Y 个最受欢迎的标签。
  2. 确定所有（或大多数）标签的频率。然后，对于每个帖子，只考虑该帖子中 X 最受欢迎的标签。这可以防止您在某些帖子中有 15 个标签的情况，从而产生大量组合列表，其中大多数永远不会发生。
  3. 对于每篇文章，只考虑长度 <= X 的组合。例如，如果一个提要有 15 个标签，那么您最终可能会得到大量组合，但其中大多数出现的次数很少，尤其是长的。所以只考虑两个或三个标签的组合。
  4. 仅扫描随机选择的 X 个提要。

希望这可以帮助！

于 2013-02-14T15:06:13.850 回答