主持人:韩朋
参会老师:杨矫云
参会学生:李雨龙,刘硕,赵春阳,程坤,段优,殷越,景波,江思源,刘杰,唐晨,贵芳
本次例会主要学习讨论了文章
Zhao Y , Karypis G , Fayyad U . Hierarchical Clustering Algorithms for Document Datasets[J]. Data Mining and Knowledge Discovery, 2005, 10(2):141-168.
研究背景:
快速和高质量的文档聚类算法通过将大量信息组织到少量有意义的聚类中,在提供直观的导航和浏览机制方面发挥着重要作用。特别是,从大型文档集合中构建有意义的层次结构的聚类算法是交互式可视化和探索的理想工具,因为它们提供了一致,可预测且具有不同粒度级别的数据视图。
问题:凝聚层次聚类方法是否产生优于分裂层次聚类方法的分层树问题
方法:
(1)综合研究并比较了使用不同标准函数和合并方案的分裂算法和凝聚算法
对于分裂聚类算法,聚类问题可以表述为计算一个聚类解,使某一特定准则函数的值最优。具体采用以下准则函数:
对于凝聚聚类算法,采用以下合并准则:
(2)提出了一种新的聚类算法,称为约束聚类算法,它结合了分裂聚类方法和凝聚聚类方法的特点,使它们能够减少了聚类方法的前期误差,提高了聚类的质量。通过分裂聚类算法获得的中间聚类来约束作出聚集决策的空间,通过使用凝聚算法为每个分裂聚类构建分层子树,然后聚类以构建最终的分层树,从而生成最终聚类结果。
实验:
实验采用了11个数据集,具体信息为:
实验结果为:
矩阵的行和列对应于各种方法,值对应于行方法优于列方法的数据集的数量。
粗体对应的是执行最好的方法,下划线对应的是仅在聚合方法或分裂方法中执行最好的方法。
列对应于约束凝聚法和分裂法中使用的标准函数。前4行为约束凝聚法与10、20、n/40、n/20约束簇和UPGMA的比较,后4行为约束凝聚法与相应分裂法的比较。每个条目中显示的值是数据集的比例。
结果分析:
1.UPGMA法在凝聚聚类算法中表现最好
2.对于大文本数据集时,分裂层次聚类算法优于凝聚层次聚类算法
3.约束的聚类方法改善了单独使用聚类或分裂方法得到的聚类解