【例会】基于相似性的层次聚类应用于文本集合

主持人:韩朋

参会老师:安宁、杨矫云

参会学生:赵春阳,贵芳,李雨龙,刘硕,明鉷,肖勇博,江思源,程坤

时间: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)使用余弦相似性代替邻近度函数计算

1

(2) 扩展到内核函数

(3)2

5.实验

数据集

3

步骤:

词袋方法,预处理:删除出现在集合中少于0.2%和超过95%的文档中的术语来应用粗略的特征选择,无停止词删除,运行tfidf加权

结果:

4

6.分析

AHC程序依赖于这种公式和稀疏的余弦相似性矩阵,不仅具有更好的可扩展性,而且还能够提供更好的聚类结果。

1.稀疏S矩阵通过去除最低相似度值来降低噪声,从而导致更好的聚类性能。

2.当两个聚类(Ci,Cj)合并在一起时,它们各自的邻域(具有分别具有Ci和Cj的非零相似性值的聚类)也被融合,使得C(ij)具有比Ci和Cj更大的邻域。

3.此外,更新规则(11)允许如果C(ij)属于两个初始邻域,则增强C(ij)与Ck的相似度值。或者可以被视为一种“传递闭包”,具有最高相似度值的对开始,并通过“可信”邻域传播相似性。

 

 

anyShare分享到:
This entry was posted in 例会. Bookmark the permalink.

发表评论