基于标签的聚类算法

Question

我希望根据他们的标签聚集许多Feed.一个典型的例子是twitter feed.每个Feed都有与之关联的用户定义标签.通过分析标签,是否可以将Feed聚类到不同的组中,并且可以根据如此多的标签来说明这么多的Feed.一个例子是 -

• 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,#earthquake - Feed1,Feed2
• #XYZ,#layoff - Feed4,Feed 5,Feed6

这里的聚类纯粹基于标签.是否有任何好的算法来实现这一目标

Answer 1

如果我正确理解了您的问题,您希望将标记聚合在一起,然后根据Feed中的标记将Feed放入这些群集中.

为此,您可以根据标记一起显示的Feed数量在标记之间创建相似性度量.对于你的例子,这将是这样的

               #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).

现在,您在标签之间有一个相似性矩阵,几乎可以使用任何适合您需求的聚类算法.因为,在运行算法之前,标签的数量可能非常大并且难以估计簇的数量,我建议使用一些非常快速的快速模块化聚类的分层聚类算法(这里参见一些细节).但是,如果您对要将其分解的群集数量有一些估计,那么Spectral群集也可能很有用(请参阅此处的一些详细信息).

将标记聚类在一起后,可以使用简单的方法将每个订阅源分配给群集.这可以非常简单,例如,计算Feed中每个群集的标记数量,并为群集分配最大匹配标记数量.

如果您对聚类策略很灵活,那么您还可以尝试以类似的方式将Feed聚类在一起,方法是根据提要之间的公共标记数创建提要之间的相似性,然后在相似度矩阵上应用聚类算法.