Clustering with Tangles: Algorithmic Framework and Theoretical Guarantees论文解读
Tangles in Clustering Methods: A Comprehensive Algorithmic Approach and Theoretical Foundations
简介：
基于"缠结"这一概念展开讨论，在数学拓扑学中"缠结"被用来证明极小定理。文中指出，在机器学习领域中应用了"缠结"概念。通过将其切割集合聚合成密集方向上的点，在此过程中这些集群则由一组统一指向的对象表示。所提出的输出结果具有层次性特征，并诱导出一种软树状分类模型。
具有极强的通用性和灵活性，并非专为单一对象分配集群成员而是通过间接引用的方式描述集群结构。这种灵活的表现形式减少了处理模糊情况的难度输入是基于数据切片集合进行操作。通过聚合较弱化的切割操作获得强化视图的数据结构在预处理阶段构建这些切割时表现出色并且适用于处理大规模数据集
贡献：
1、将复杂的抽象概念从数学理论应用到机器学习领域中，并开发出灵活适应性强的聚类系统。
2、展示其灵活性，在问卷调查场景、图聚类场景以及基于特征分析时提供具体案例研究。
3、在上述三个分析框架下给出理论支持，并揭示问卷统计模型中的本质规律；此外，在基于特征分析时展现出良好的可解释性。
4、实现核心组件的不同选项，并根据需求选择预处理或后处理的方式。
缠结算法的框架：
找到原始切割集、定向切割以识别缠结和后处理缠结进行聚类。
构建原始切割集：
- 调查表形式主要采用二分法的选择。
- KL算法生成起始划分，并在欧几里得空间中实现聚类。
定义切割的损失函数（相似性之和）：c({A,A^C}) = \sum{sim(v,w)}
根据切割识别缠结：
尝试每一个一致性的方向都是不可行的 因此必须放弃这一策略 于是转而设计一种基于树结构的搜索方案以有效解决此问题 这种方法将确保搜索树结构能够涵盖所有可能的分割方式 并且其结果将形成一个带有标记节点的标准二叉树结构
将缠结处理为软聚类或硬聚类：
算法1：
第一步建立一个空树; 该结构包含一个根节点; 根据评估标准将切口按照成本函数进行排序; 规定处理切口顺序以确定其优先级. 接着依次处理排序后的切口; 对于每一个切口; 审查当前层级的所有项(即'tree'节点); 当某一项与当前切口相匹配时; 将其创建为该项的新子项. 重复上述操作直至所有切口均被处理完毕. 最终构建完成了一个用于分析数据聚类模式的搜索结构; 每个'tangle'指向对应的数据区域.
针对生成模型中的分层切分机制进行深入分析：
着重分析导致数据分裂的连接点（tangle），其左、右子树分别指向各自的数据密集区域，并避免考虑无法反映聚类结构特性的切分线。
对于每一个切分点（tangle），识别出那些决定将数据划分为独立区域的关键切分线，并将其作为节点特征集的基础要素。
从树根节点出发逐步解析每个分支节点的情况：首先确定该节点对应的特征集合；然后递归地对其左、右子节点执行同样的特征提取与划分操作；最终整合所有结果形成一个精简化的基于切分机制的凝聚树状结构模型；最后在构建完成后的层次结构中为每个核心切分点分配概率值表征对象属于该层次的可能性大小
基于每个分裂tangle都被赋予相应的概率权重P(t)后，则可使得数据能够被有效地进行软聚类分析；这种机制还能够确保每个对象能够同时关联到多个不同的簇中。
针对每一个数据样本及其对应的切割方式，在计算其在该方向上的切割次数相对于所有切割总数的比例时（考虑到不同切割的重要性差异），我们引入了一个非递增权重函数h来进行加权处理；通过这种处理方法，在后续步骤中最终确定每一个样本及其对应切割是否归属于右侧子树的可能性。
实施软聚类：每个数据点被分配到各个潜在聚类中，并带有相应的隶属概率；通过之前确定的分割方式以及关键步骤来进行。
给定一棵树结构，在其中每一个数据点v抵达树中的任意一个节点t时都会被赋予一个几率p_t(v)；其值等于从根节点到节点\tau的所有边上概率的乘积。
处理成硬聚类：对于数据点保留归属簇概率值最大的类别
实验数据分析：
实验一：问卷场景
切割集合：直接根据回答是或不是来生成切割集
实验二：图数据场景
实验三：基于特征的数据和可解释性场景
算法2：生成初始切割集合
基本思路是基于一个初始的近似均衡切割开始，并逐步增加切分数。每一次选择都是为了确保新切割一侧所包含的点的数量与给定的参数a相关联，并最终构建出一个具有多样性的切割集合。
计算纠缠速度很快：
如图14所示，在k-means算法的基础上具有相似的特性表现上，在谱聚类算法中表现出持续稳定的优秀效果（效果显著），但其运行速度明显较低（速度较慢）。
切割的可解释性转化为可解释的聚类：
基于纠缠搜索树在不同主题下可演变出多种方法用于解释获得的缠结。
结论：
1、开发出一个具有实际应用价值的基础架构，并通过三种统计模型提供了理论支持。
指向某一聚类的基本概念是对一般聚类问题的灵活表述方式之一,仅需数据集的一组切割及对象间相似性的某种度量即可定义。
因此,纠缠可以直接应用于众多数据集,无需通过构建最近邻图或嵌入节点等变通方法。
2、虽然数值评估时会将输出转换为硬聚类结果,但其实质属于软聚类的一种形式。
3、本研究首次系统性地探讨了纠缠在聚类分析中的潜在应用。
4、未来待解决的问题主要有两个:其一是探索算法层面初始切割与纠缠算法的最佳交互;其二是理论层面如何将弱切割转化为强聚类这一关键问题尚待解决。