主持人:韩朋
参会老师:阙夏、杨矫云
参会学生:明鉷,肖勇博,韩朋,刘硕,李雨龙,赵春阳,程坤,哈山
请假学生:唐晨,段优,滕越,景波,江思源,刘杰
时间:2018年9月5日
本次例会学习讨论了以下文章:
Beil F, Ester M, Xu X. Frequent term-based text clustering[J]. Proceedings of Int.conf.on Knowledge Discovery & Data Mining, 2002.
当前在谷歌学术的被引量为656.
一、背景(background)
由于网络和组织内部网的文档额巨大规模,高动态性和多样性,为某些用户或目的找到真正相关的内容已成为一项非常具有挑战性的任务。例如,标准网络搜索引擎具有低精度,因为通常将大量不相关的网页与少量相关页面一起返回。
二、问题(Problem)
数据的维度高:需要处理稀疏数据空间的能力或降维的方法。
数据库大:聚类算法必须非常高效并且可以扩展到大型数据库。
三、假设(Hypothesis)
提出了一种基于频繁项(词)集进行文本聚类的方法
四、方法(Method)
基于频繁项的聚类方法:提供了一种减少文档向量空间大维度的自然方法。
使用频繁术语集相对于它们的支持文档集(集群)的相互重叠来确定集群。这种方法背后的基本原理是,当集群稍后用于对新文档进行分类时,集群的小重叠将导致小的分类错误。
FTC(Frequent Term-based Clustering):确定一个平面聚类,即覆盖整个数据库的一组非结构化的聚类。
HFTC(Hierarchical Frequent Term-based Clustering):确定层次聚类,即具有每个集群与其在层次结构中的前辈之间的子集关系的图形结构聚类。
五、实验(Experiment)
数据集包括三类,分别来自经典、路透社和WAP,
实现了FTC,HFTC和k-means变体算法,并尽可能使用相同的类。
六、结果分析(Analysis)
FTC评估:在所有实验中,FTC产生的簇质量与二等分和9等分k-均值相当。
但是,FTC在所有测试数据集上的效率明显高,FTC在经典数据(22个集群)上的表现优于最佳竞争对手6倍,路透社数据(50个集群)的性能提高了2倍。
HFTC发现重叠簇。
七、展望(Future work)
HFTC生成的层次化聚类的层次结构更容易浏览和更易于理解。
其他范例如动态规划也可能被用来解决频繁的基于术语的聚类问题,应该加以探索。 对于许多应用来说,分层聚类是特别感兴趣的。 然而,众所周知的层次聚类质量并不能从用户的角度充分捕捉。 应该为此目的开发新方法。 所提出的聚类算法具有有希望的应用,例如web搜索引擎的前端,市场细分等