主持人:韩朋
参会老师:安宁、杨矫云
参会学生:赵春阳,贵芳,李雨龙,刘硕,明鉷,肖勇博,江思源,程坤
时间:2018年11月14日
本次例会学习讨论了以下文章:
Ah-Pine J, Wang X. Similarity Based Hierarchical Clustering with an Application to Text Collections[M]// Advances in Intelligent Data Analysis XV. Springer International Publishing, 2016:320-331.
1. 层次聚类
层次聚类在不同层次对数据集进行划分,从而形成树形的聚类结构。数据集划分可采用“自底向上”的聚合策略,也可采用“自顶向下”的分拆策略。
分裂层次聚类(自上而下):在分割有N个实例的数据集时,存在2N-1-1种可能将数据集分为两个聚类。
凝聚分层聚类(自下而上):给定N个实例的数据集D,每个步骤递归地合并两个聚类,直到所有实例被分组到一个聚类中。
结果通常由树形图表示,树形图是由2N-1个节点组成的二叉树,有高度。
AHC的传统过程,也称为存储的相异性方法,采用大小为N的成对比较矩阵D作为输入,用具有0高度值的N个初始结点(单例)初始化二叉树,并迭代地添加新节点(合并的簇)融合一对簇(C_i,C_j)确定如下:
(C_i,C_j )=(arg min)┬((C_k,C_l ) )D(C_k,C_l ) (1)
时间复杂度O(N3)
LW公式:用于在每次迭代时更新相异度矩阵D的通用方程
C_((ij) )=C_i 〖∪C〗_j
D(C_((ij) ) ,C_k) =”α” _iD(C_i, C_k) + “α” _j D(C_j, C_k) + βD(C_i, C_j) + γ|D(C_i, C_k)−D(C_j, C_k)| (2)
D(.,.)可以理解为邻近度函数
2. 问题
AHC的计算成本高。
3.假设
(1)使用余弦相似性得到的结果等效LW公式得到的结果
(2)提出的方法可以扩展到内核函数
(3)余弦相似矩阵的稀疏化可以减少内存使用
4.方法
(1)使用余弦相似性代替邻近度函数计算
(2) 扩展到内核函数
5.实验
数据集
步骤:
词袋方法,预处理:删除出现在集合中少于0.2%和超过95%的文档中的术语来应用粗略的特征选择,无停止词删除,运行tfidf加权
结果:
6.分析
AHC程序依赖于这种公式和稀疏的余弦相似性矩阵,不仅具有更好的可扩展性,而且还能够提供更好的聚类结果。
1.稀疏S矩阵通过去除最低相似度值来降低噪声,从而导致更好的聚类性能。
2.当两个聚类(Ci,Cj)合并在一起时,它们各自的邻域(具有分别具有Ci和Cj的非零相似性值的聚类)也被融合,使得C(ij)具有比Ci和Cj更大的邻域。
3.此外,更新规则(11)允许如果C(ij)属于两个初始邻域,则增强C(ij)与Ck的相似度值。或者可以被视为一种“传递闭包”,具有最高相似度值的对开始,并通过“可信”邻域传播相似性。