主持人：韩朋
参会老师：安宁、杨矫云
参会学生：赵春阳，贵芳，李雨龙，刘硕，明鉷，肖勇博，江思源，程坤
时间：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） 扩展到内核函数
（3）
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的相似度值。或者可以被视为一种“传递闭包”，具有最高相似度值的对开始，并通过“可信”邻域传播相似性。