Jan, 2015

在聚类性假设下聚类的计算可行性

PDF
TL;DR本文探讨了聚类的困难性和可聚类性的主题。作者提出了以前的研究和对聚类簇合法性的批判性评估。虽然我们相信聚类只有在数据不重要时才是困难的，但我们认为这个 CDNM 论点仍远未得到正式的实质性证明。在阐述了聚类簇合法性的基本要求后，本文评估了这些要求的现有结果，并概述了一些研究挑战和开放问题。
clusteringnp-hardclusterabilityefficiencyresearch challenges
发现论文，激发创造
  • 只有在聚类无关紧要时才很困难

    本文提出了一个基于度量空间的 “好聚类” 的理论框架，展示了如果存在好的聚类，则在许多情况下可以轻易地找到它，因此与流行观点相反，聚类不应被视为一项艰苦的任务。

    May, 2012

  • 可解释聚类与可区分性标准

    基于全局的可区分性准则，本文提出了用于验证聚类分析结果以及确定数据集中聚类数量的方法，并将该准则与常用的聚类方法进行了整合，包括层次聚类、k-means 和有限混合模型。通过模拟研究和实际数据应用，我们展示了这些新算法的结果。

    Apr, 2024

  • 信息熵聚类探秘

    该研究提出一种基于信息论原理且无需参数假设的数据聚类新方法，将信息论用于无偏见的数据分类可能会从根本上导致聚类性能恶化，而作者们则基于信息论的基本概念，提出了一种新的聚类度量方法，通过对有限数据的粗粒化一致性来定义含义。

    Oct, 2013

  • 聚类的唯一性定理

    本文采用公理化方法研究聚类理论，提出一套符合逻辑的公理并通过对单联通聚类函数的抽象属性进行分类，为用户提供了选择合适聚类范例的指导。

    May, 2012

  • 广泛间隔与聚类公理

    这篇研究论文介绍了对 k-means 算法的扩展，以符合 Kleinberg 的公理系统，并提出了新的聚类性质，进一步解释了算法的特点和适用性。

    Aug, 2023

  • 基于信息的聚类

    该研究采用信息理论的视角来重新构造聚类问题，避免了许多现有聚类方法所依赖的非常规结构的假设，且捕捉了非线性关系。基于集体相似度而非传统的成对度量，该方法在不同领域内都表现出比现有算法更高的聚类一致性。

    Nov, 2005

  • 数据易于 (对于 K-Means)

    该论文研究了 $k$-means 算法的能力，正确地恢复互相分离的簇群。基于常见的簇群定义，考虑了簇内同质性和簇间多样性的要求，并找到了一种特殊情况的互相分离簇群，使得 $k$-means 的代价函数全局最小值与互相分离性一致。通过实验发现各种 $k$-means 品牌实际上无法发现互相分离的簇群，因此提出了一种新的算法，通过重复子抽样选择种子的方式，对 $k$-means++ 进行变体改进，并在任务中胜过 $k$-means 系列中的其他四种算法。

    Aug, 2023

  • 测试图的聚类能力：算法和下限

    本文提出了一种利用角度信息和奇异值分解的子线性时间图聚类算法，并在其基础上给出了测试聚类可行性的查询复杂度下界，并且通过这些技术，也实现了新的子线性时间下界近似最大割价值的问题。

    Aug, 2018

  • 加权聚类

    通过一种新的方法，我们明确和形式上展示了 center-based 方法在某些应用程序中的优越性。

    Sep, 2011

  • 定数个簇的相关聚类

    研究聚类分析中的一种新方法 —— 相关聚类或定性信息聚类，探讨了最大化协议的问题和最小化分歧的问题，重点研究了聚类数为常数 k 的情况，发现该问题具有多项式时间近似解，为解决最小化分歧问题做了大量的技术工作。

    Apr, 2005