The Wayback Machine - https://web.archive.org/web/20221025180834/https://baike.sogou.com/kexue/d10772.htm

k平均算法

编辑

k-means聚类是一种矢量量化方法，最初源于信号处理，在数据挖掘中常用于聚类分析。 k-means聚类旨在将 n个观察值划分为 k 个聚类，其中每个观测值属于具有最近均值所在的聚类，它作为聚类的原型，可以将数据空间划分成沃罗诺伊单元。

这个问题计算困难；然而，高效的启发式算法很快收敛到局部最优。对于高斯分布的混合，通过两者采用的迭代精化方法，这些通常类似于期望最大化算法k-means 和 高斯混合建模。他们都使用集群中心来模拟数据；然而， k-means聚类倾向于找到空间范围相当的聚类，而期望最大化机制允许聚类具有不同的形状。

k-means与 k最近邻分类器（一种流行的机器学习分类技术）经常因为相似的名字而混淆。将1-最近邻分类器应用于通过以下方式获得的聚类中心 k-means将新数据分类到现有集群中。这被称为最近质心分类器或Rocchio算法。

1 描述编辑

给定一组观察值(x1，x2，…，xn)，其中每个观察都是一个 d-维实向量， k-means聚类旨在划分 n 对...的观察 k (≤ n)集S = {S1, S2, …， Sk以便最小化群内平方和(WCSS)(即方差)。正式来说，目标是找到:

 

其中 μi 是指 Si。这相当于最小化同一个群中的点的成对平方偏差:

 

等价可以从恒等式中推导出来   。因为总方差是常数，这相当于最大化 不同的 聚类(聚类间平方和，BCSS)， 这遵循总方差定律。

2 历史编辑

术语“k-means是詹姆斯·麦克奎恩在1967年首次使用，[1] 尽管这个想法可以追溯到1956年的雨果·施泰因豪斯。[2] 贝尔实验室的斯图尔特·劳埃德于1957年首次提出标准算法作为脉冲编码调制技术，尽管直到1982年才作为期刊文章发表。[3] 1965年，E. W .福吉发表了基本相同的方法，这就是为什么它有时被称为劳埃德-福吉。[4]

3 算法编辑

3.1 标准算法

k-means的收敛过程

最常见的算法使用迭代细化技术。由于其无处不在，它通常被称为 k-均值算法；它也被称为劳埃德算法，特别是在计算机科学领域。

给定一组初始的 k means 聚类m1(1)，…，mk(1) (见下文)，算法在两个步骤之间交替进行:[5]

分配步骤:将每个观察值分配给其均值具有最小平方欧几里得距离的聚类，这直观上是“最近”的均值。  [6] (数学上，这意味着根据由该方法生成的沃罗诺伊图来划分观测值)。

     

其中每个       被分配给一个      ，即使它可以分配给其中的两个或多个。

更新步骤:计算新聚类中观察值的新均值(质心)。

     

当分配不再改变时，算法已经收敛。该算法不能保证找到最优解。[7]

该算法通常表现为通过距离将对象分配给最近的聚类。使用不同于(平方)欧几里得距离的距离函数可能会阻止算法收敛。因此 k-means的诸多变种(例如：球状的 k-means和 k-medoids)被提出来使得可以使用其他距离测量方法。

初始化方法

常用的初始化方法有Forgy和Random Partition。[8] Forgy方法随机选择 k 并使用这些作为初始手段。随机划分方法首先为每个观察值随机分配一个聚类，然后进行更新步骤，从而计算初始平均值作为聚类随机分配点的质心。Forgy方法倾向于将初始均值分散开来，而随机分区将它们都放在靠近数据集中心的位置。根据哈默利等人的说法，[8] 随机划分方法通常更适合于如下算法 k-谐波均值和模糊 k-means。为了期望最大化和标准 k-means算法，最好使用Forgy初始化方法。由雪拉比等人进行的综合研究，[9] 然而，发现流行的初始化方法，如Forgy，Random Partition和Maximin往往表现不佳，而布拉德利和法耶兹的方法[10] 在“最佳团队”中表现“一致”,并且 k-means++表现“一般很好”。

  • Demonstration of the standard algorithm

  • 1. 初始化k 个“均值”（在当前情况下，k = 3）是在数据域内随机生成的（以彩色显示）。

  • 2. 根据各个点与最近的均值的相似度来创建k个簇。这里的分区是由均值生成的Voronoi图。

  • 3. 这个k个簇的中心点成为新的均值.

  • 4. 重复步骤2和3直到收敛为止

该算法不能保证收敛到全局最优。结果可能取决于初始聚类。由于算法通常速度很快，通常在不同的启动条件下运行多次。然而，最坏情况下的性能可能会很慢:特别是某些点集，即使在二维空间中，也会以指数时间收敛，也就是说

2Ω(n)。[11] 这些点集在实践中似乎并没有出现:这一点被以下事实所证实 k-means是多项式。[12]

“分配”步骤被称为“期望步骤”，而“更新步骤”是最大化步骤，使该算法成为 广义的 期望最大化算法。

3.2 复杂性

寻找最佳解决方案 k-means中观察的聚类问题 d 尺寸为:

  • 一般欧几里得空间中的NP-hard d 维度)即使对于两个集群，[13][14][15][16]
  • NP-适用于一般数量的集群 k 即使在飞机上，[17]
  • 如果 k 和 d (维度)是固定的，问题可以及时得到准确解决    ，其中 n 要聚集的实体数量。[18]

因此，通常使用各种启发式算法，如上面给出的劳埃德算法。

劳埃德算法(和大多数变体)的运行时间是   ,[7][19] 其中:

  • n 是的数量 d-维度向量(待聚类)
  • k 集群的数量
  • i 收敛前所需的迭代次数。

在具有聚类结构的数据上，直到收敛的迭代次数通常很少，并且结果在前十几次迭代后仅略有改善。劳埃德算法因此在实践中经常被认为是“线性”的复杂性，尽管它在最坏的情况下是在收敛之前执行的超大项。[20]

  • 在最坏的情况下，劳埃德算法需要     迭代，所以劳埃德算法的最坏情况复杂性是超大项。[20]
  • 劳埃德保险公司 k-means算法具有多项式平滑运行时间。结果表明[12] 对于任意集合 n 指向    ，如果每个点都被平均值为正态分布独立扰动 0 和方差    ，则预期的运行时间为 k-means算法的边界为    ，这是一个多项式 n, k, d 和    。
  • 对于简单的情况，证明了更好的界限。例如，在 [21] 结果表明 k-means算法的边界为     为 n 整数格中的点    。

劳埃德算法是解决这个问题的标准方法。然而，它花费大量的处理时间来计算k个集群中心和n个数据点之间的距离。由于经过几次迭代后，点通常保持在同一个集群中，所以很多工作是不必要的，这使得简单的实现非常低效。一些实现使用缓存和三角不等式来创建边界并加速劳埃德算法。[7][22][23][24][25]

3.3 变种

  • 詹克斯自然休息优化: k-means应用于单变量数据的方法
  • k-medians聚类使用每个维度的中位数而不是平均值，这样可以最小化     诺姆(曼哈顿距离)。
  • k-medoid(也称为:围绕medoid分区，PAM)使用medoid而不是均值，这样可以最小化 任意的 距离函数。
  • 模糊C均值聚类是 k-means每个数据点属于每个聚类的模糊程度。
  • 用期望最大化算法算法训练的高斯混合模型保持对聚类的概率分配而不是确定性分配，以及多变量高斯分布而不是均值。
  • k-means++选择初始中心的方式给出了一个关于WCSS目标的可证明上界。
  • HG-means是K-means的复杂扩展，它通过迭代重组步骤和K-means改进阶段逃离局部极小值[26]
  • 过滤算法使用kd树来加速每一个 k-means是台阶。[27]
  • 有些方法试图加快每种方法的速度 k-means使用三角不等式的步骤。[22][23][24][28][25]
  • 通过在集群之间交换点来避开本地optima。[7]
  • 球形 k-均值聚类算法适用于文本数据。[29]
  • 分层变体，如二分类 k-means是，[30] x均值聚类[31] 和G-均值聚类[32] 重复分割集群以构建层次结构，还可以尝试自动确定数据集中的最佳集群数量。
  • 集群轮廓等内部集群评估措施有助于确定集群数量。
  • 闵可夫斯基加权 k-means自动计算特定于集群的特征权重，支持一个特征在不同特征上可能具有不同程度相关性的直观想法。[33] 这些权重也可用于重新缩放给定数据集，增加了在预期的聚类数下优化聚类有效性指数的可能性。[34]
  • 小批量 k-means: 对不适合内存的数据集使用“小批量”样本的k-means变种。[35]

3.4 哈迪根-黄方法

哈迪根和黄氏方法[7] 提供了一种更复杂但计算成本更高的执行方式 k-means是。这仍然是一种启发式方法。

   个人成本是    定义为   ，与    集群的中心。

分配步骤:哈迪根和王的方法开始于将点分成随机的簇   。

更新步骤:接下来它确定    和    以下函数达到最小值

  

为了    达到这个最小值，   从群集中移出    到集群   。

终止:算法终止一次    对所有人来说都大于零   。

该算法可以通过立即移动来加速    来自集群    到集群    一旦    已经找到了   。这种加速会使最终结果的成本更高。

功能    可以通过利用等式相对有效地评估[36]

  

4 讨论编辑

本图是k-means收敛到局部最小值的典型例子。在这个例子中，k-means聚类的结果（右图）与数据集的明显聚类结构相矛盾。小圆圈是数据点，四个射线星是质心（均值）。初始配置在左图中。该算法在从左到右呈现在图上的五次迭代之后收敛。插图是使用Mirkes Java applet编写的.[1]

k-means聚类结果为鸢尾花数据集和使用ELKI可视化的实际物种。使用较大的半透明符号标记聚类均值。

k-means聚类与人工数据集（“鼠标”）上的EM聚类。k均值产生相等大小的簇的趋势导致这里的结果不好，而EM受益于数据集中存在的具有不同半径的高斯分布。

k-means的三个关键特性使得它的效率很低这通常被认为是其最大的缺点:

  • 欧几里得距离被用作度量，方差被用作聚类散布的度量。
  • 集群的数量 k 是一个输入参数:对 k 可能会产生糟糕的结果。这就是为什么在表演时 k-means，运行诊断检查以确定数据集中的集群数量非常重要。
  • 收敛到局部最小值可能会产生违反直觉(“错误”)的结果(见图)。

k-means的主要限制 是它的集群模型。这个概念是基于可分离的球状星团，使平均值向星团中心收敛。这些群集的大小应该相似，因此分配到最近的群集中心是正确的。当例如应用时 k-means值为    在著名的安德森鸢尾花卉数据集鸢尾上，结果往往不能分离出包含在数据集中的三种鸢尾。随着   两个可见的星团(一个包含两个物种)将被发现    两个集群中的一个将被分成两个偶数部分。事实上，    更适合这个数据集，尽管数据集包含3 班。如同任何其他聚类算法一样 k-means结果假设数据满足某些标准。它在一些数据集上运行良好，但在其他数据集上却失败了。

的结果 k-means可以看作是簇means的Voronoi细胞。由于数据在群集方式之间被拆分了一半，这可能导致次优的拆分，如“鼠标”示例所示。由期望最大化算法使用的高斯模型(可以说是 k均值)通过同时具有方差和协方差而更加灵活。因此，电磁结果能够更好地适应不同大小的簇 k-均值以及相关聚类(本例中没有)。 K-均值与非参数贝叶斯建模密切相关。[37]

5 应用程序编辑

k-means聚类非常容易应用于甚至大型数据集，特别是当使用启发式算法(如劳埃德算法)时。它已经成功地应用于市场细分、计算机视觉和天文学等许多领域。它经常被用作其他算法的预处理步骤，例如找到一个起始配置。

5.1 矢量量化

双通道(仅供演示使用——红色和绿色)彩色图像。

使用k均值将上图中存在的颜色矢量量化为Voronoi单元。

k-means起源于信号处理，在这个领域仍然有用。例如，在计算机图形学中，颜色量化是将图像的调色板减少到固定数量的颜色的任务 k。这 k-means算法可以很容易地用于此任务，并产生有竞争力的结果。这种方法的一个用例是图像分割。矢量量化的其他用途包括非随机采样，如 k-方法可以很容易地用于选择 k 用于进一步分析的来自大数据集的不同但原型的对象。

5.2 聚类分析

在聚类分析中 k-means算法可用于将输入数据集划分为 k 分区(集群)。

然而，纯粹的 k-means算法不是很灵活，因此用途有限(除非上述矢量量化实际上是期望的用例)。特别是，参数 k 已知在没有外部约束的情况下很难选择(如上所述)。另一个限制是它不能用于任意距离函数或非数字数据。对于这些用例来说，许多其他算法都是优越的。

5.3 表征学习

k-means着聚类已经被用作(半)监督学习或无监督学习中的特征学习(或字典学习)步骤。[38] 基本方法是首先使用输入训练数据(无需标记)训练一个 k-means聚类表示。然后，为了将任何输入数据投影到新的特征空间中，“编码”函数，例如数据与质心位置的阈值矩阵乘积，计算从数据到每个质心的距离，或者简单地计算最近质心的指示函数，[38][39] 或者距离的平滑变换。[40] 或者，通过高斯径向基函数变换样本-聚类距离，获得径向基函数网络的隐藏层。[41]

这种使用 k-means已经成功地与简单的线性分类器相结合，用于NLP中的半监督学习(特别是命名实体识别)[42] 在计算机视觉中。在物体识别任务中，它被发现与更复杂的特征学习方法如自动编码器和受限玻尔兹曼机表现出相当的性能。[40] 然而，为了获得同等的性能，它通常需要更多的数据，因为每个数据点只贡献一个“特性”。[38]

6 与其他算法的关系编辑

6.1 高斯混合模型

k-means聚类及其相关的期望最大化算法是高斯混合模型的一个特例，特别是将所有协方差视为对角线、相等和小的极限。概括一个 k-means问题进入高斯混合模型。[43] 另一个概括是 k-means算法是K-SVD算法，它将数据点估计为“码本向量”的稀疏线性组合。 k-means对应于使用权重为1的单个码本矢量的特殊情况。[44]

6.2 主成分分析

k-means聚类的类别个数是由主成分分析给出。[45][46] 主方向跨越的主成分分析子空间与聚类质心子空间相同。直觉是 k-means描述球形(球状)簇。如果数据有2个簇，连接两个质心的线是最佳的一维投影方向，也是第一个主成分分析方向。在质量中心切割直线会将聚类分开(这是离散聚类指示器的连续松弛)。如果数据有三个簇，由三个簇质心跨越的二维平面是最好的二维投影。该平面也由前两个主成分分析维度定义。分离良好的星系团被球形星系团有效地模拟，因此被 k-means是。当它们靠近时，非球形的星团很难分离。例如，当投射到主成分分析子空间上时，两个在空间中缠绕的半月形星团不能很好地分离。 k-不应该期望方法在该数据上表现良好。[47] 对于聚类质心子空间由主方向跨越的说法，很容易产生反例。[48]

6.3 平均移位聚类

基本的均值漂移聚类算法保持一组与输入数据集大小相同的数据点。最初，该集合是从输入集合中复制的。然后这个集合被集合中那些在给定距离内的点的平均值反复替换。相比之下， k-means将此更新集限制为 k 点通常比输入数据集中的点数少得多，并且用 输入集 比任何其他点都更接近该点(例如，在每个更新点的沃罗诺伊分区内)。一种平均移位算法，类似于 k-means是，叫做 似然均值漂移，用输入集合中在变化集合的给定距离内的所有点的平均值替换正在替换的点的集合。[49] 均值漂移的优势之一 k-means集群的数量没有预先指定，因为如果只存在少量集群，则均值漂移可能只找到少数集群。然而，均值漂移可能比 k-means并且仍然需要选择带宽参数。均值漂移有软变量。

6.4 独立成分分析

在稀疏性假设下，当输入数据用白化变换预处理时， k-means产生线性独立分量分析(ICA)任务的解。这有助于解释 k-以学习为特色的方法。[50]

6.5 双边过滤

k-means隐式假定输入数据集的顺序无关紧要。双向过滤器类似于 k-means和mean shift，因为它维护一组被means迭代替换的数据点。然而，双边滤波器将(核加权)平均值的计算限制为仅包括输入数据排序中接近的点。[49] 这使得它适用于图像去噪等问题，其中图像中像素的空间排列至关重要。

7 类似的问题编辑

最小化群集函数的平方误差集还包括 k-medoids算法，一种强制每个簇的中心点成为实际点之一的方法，即使用medoids代替质心。

8 软件实现编辑

该算法的不同实现表现出性能差异，测试数据集上最快的在10秒内完成，最慢的花费25，988秒(~7小时)。[51] 这种差异可以归因于实现质量、语言和编译器的差异、不同的终止标准和精度级别，以及加速索引的使用。

8.1 自由软件/开源

以下实现在自由/开源软件许可证下可用，源代码公开。

  • Accord.NET包含的C#实现 k-means， k-means++和 k-modes。
  • ALGLIB包含并行化的C与C++程序设计学习与实验系统和C#实现 k-means和 k-means++。
  • AOSP包含一个Java实现 k-means。
  • CrimeStat实现了两个空间 k-means算法，其中一种算法允许用户定义起始位置。
  • ELKI包含 k-means(劳埃德和麦克奎恩迭代，以及不同的初始化，例如 k-means++初始化)和各种更高级的聚类算法。
  • Julia包含一个 k-means在JuliaStats集群包中实现。
  • KNIME包含以下节点 k-means和 k-medoids。
  • Mahout包含一个基于MapReduce的 k-means。
  • mlpack在C与C++程序设计学习与实验系统实施了 k-means算法。
  • Octave含 k-means。
  • OpenCV包含一个 k-means实施。
  • Orange包括一种成分，用于 k-指自动选择的聚类 k 和群集轮廓评分。
  • PSPP包含 k-means快速群集命令执行 k-means数据集上的聚类。
  • R包含三个 k-means变种。
  • SciPy和scikit-learn包含多个 k-means实现。
  • Spark MLlib实现了一个分布式 k-means算法。
  • Torch包含一个 unsup 提供 k-means集群。
  • Weka包含 k-means和 x-means算法。

8.2 所有人

以下实现在专有许可条款下可用，并且可能没有公开可用的源代码。

  • Ayasdi
  • MATLAB
  • Mathematica
  • RapidMiner
  • SAP HANA
  • 斯堪的纳维亚航空公司
  • SPSS
  • Stata
  • OriginPro

参考文献

  • [1]

    ^MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1. University of California Press. pp. 281–297. MR 0214227. Zbl 0214.46201. Retrieved 2009-04-07..

  • [2]

    ^Steinhaus, H. (1957). "Sur la division des corps matériels en parties". Bull. Acad. Polon. Sci. (in French). 4 (12): 801–804. MR 0090073. Zbl 0079.16403.CS1 maint: Unrecognized language (link).

  • [3]

    ^Lloyd, S. P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper. Published in journal much later: Lloyd., S. P. (1982). "Least squares quantization in PCM" (PDF). IEEE Transactions on Information Theory. 28 (2): 129–137. CiteSeerX 10.1.1.131.1338. doi:10.1109/TIT.1982.1056489. Retrieved 2009-04-15..

  • [4]

    ^E.W. Forgy (1965). "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics. 21 (3): 768–769. JSTOR 2528559..

  • [5]

    ^MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292. ISBN 978-0-521-64298-9. MR 2012999..

  • [6]

    ^Since the square root is a monotone function, this also is the minimum Euclidean distance assignment..

  • [7]

    ^Hartigan, J. A.; Wong, M. A. (1979). "Algorithm AS 136: A k-Means Clustering Algorithm". Journal of the Royal Statistical Society, Series C. 28 (1): 100–108. JSTOR 2346830..

  • [8]

    ^Hamerly, G.; Elkan, C. (2002). "Alternatives to the k-means algorithm that find better clusterings" (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM)..

  • [9]

    ^Celebi, M. E., Kingravi, H. A., and Vela, P. A. (2013). "A comparative study of efficient initialization methods for the k-means clustering algorithm". Expert Systems with Applications. 40 (1): 200–210. arXiv:1209.1960. doi:10.1016/j.eswa.2012.07.021.CS1 maint: Multiple names: authors list (link).

  • [10]

    ^Bradley, Paul S.; Fayyad, Usama M. (1998). "Refining Initial Points for k-Means Clustering". Proceedings of the Fifteenth International Conference on Machine Learning..

  • [11]

    ^Vattani., A. (2011). "k-means requires exponentially many iterations even in the plane" (PDF). Discrete and Computational Geometry. 45 (4): 596–616. doi:10.1007/s00454-011-9340-1..

  • [12]

    ^Arthur, D.; Manthey, B.; Roeglin, H. (2009). "k-means has polynomial smoothed complexity". Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS). arXiv:0904.1113..

  • [13]

    ^Garey, M.; Johnson, D.; Witsenhausen, H. (1982-03-01). "The complexity of the generalized Lloyd - Max problem (Corresp.)". IEEE Transactions on Information Theory. 28 (2): 255–256. doi:10.1109/TIT.1982.1056488. ISSN 0018-9448..

  • [14]

    ^Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar (1998-12-01). "A Microeconomic View of Data Mining". Data Mining and Knowledge Discovery (in 英语). 2 (4): 311–324. doi:10.1023/A:1009726428407. ISSN 1384-5810..

  • [15]

    ^Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P. (2009). "NP-hardness of Euclidean sum-of-squares clustering". Machine Learning. 75 (2): 245–249. doi:10.1007/s10994-009-5103-0..

  • [16]

    ^Dasgupta, S.; Freund, Y. (July 2009). "Random Projection Trees for Vector Quantization". IEEE Transactions on Information Theory. 55 (7): 3229–3242. arXiv:0805.1390. doi:10.1109/TIT.2009.2021326..

  • [17]

    ^Mahajan, M.; Nimbhorkar, P.; Varadarajan, K. (2009). The Planar k-Means Problem is NP-Hard. Lecture Notes in Computer Science. 5431. pp. 274–285. CiteSeerX 10.1.1.331.1306. doi:10.1007/978-3-642-00202-1_24. ISBN 978-3-642-00201-4..

  • [18]

    ^Inaba, M.; Katoh, N.; Imai, H. (1994). Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering. Proceedings of 10th ACM Symposium on Computational Geometry. pp. 332–339. doi:10.1145/177424.178042..

  • [19]

    ^D., Manning, Christopher (2008). Introduction to information retrieval. Raghavan, Prabhakar., Schütze, Hinrich. New York: Cambridge University Press. ISBN 978-0521865715. OCLC 190786122..

  • [20]

    ^Arthur, David; Vassilvitskii, Sergei (2006-01-01). How Slow is the k-means Method?. Proceedings of the Twenty-second Annual Symposium on Computational Geometry. SCG '06. New York, NY, USA: ACM. pp. 144–153. doi:10.1145/1137856.1137880. ISBN 978-1595933409..

  • [21]

    ^Arthur; Abhishek Bhowmick (2009). A theoretical analysis of Lloyd's algorithm for k-means clustering (PDF) (Thesis). Archived from the original (PDF) on 2015-12-08..

  • [22]

    ^Phillips, Steven J. (2002-01-04). "Acceleration of K-Means and Related Clustering Algorithms". In Mount, David M.; Stein, Clifford. Acceleration of k-Means and Related Clustering Algorithms. Lecture Notes in Computer Science. 2409. Springer Berlin Heidelberg. pp. 166–177. doi:10.1007/3-540-45643-0_13. ISBN 978-3-540-43977-6..

  • [23]

    ^Elkan, C. (2003). "Using the triangle inequality to accelerate k-means" (PDF). Proceedings of the Twentieth International Conference on Machine Learning (ICML)..

  • [24]

    ^Hamerly, Greg. "Making k-means even faster". CiteSeerX 10.1.1.187.3017..

  • [25]

    ^Hamerly, Greg; Drake, Jonathan (2015). Accelerating Lloyd's algorithm for k-means clustering. Partitional Clustering Algorithms. pp. 41–78. doi:10.1007/978-3-319-09259-1_2. ISBN 978-3-319-09258-4..

  • [26]

    ^Gribel, D. and Vidal, T. (2019). "HG-means: A scalable hybrid metaheuristic for minimum sum-of-squares clustering". Pattern Recognition. 88 (1): 569–583. arXiv:1804.09813. doi:10.1016/j.patcog.2018.12.022.CS1 maint: Multiple names: authors list (link).

  • [27]

    ^Kanungo, T.; Mount, D. M.; Netanyahu, N. S.; Piatko, C. D.; Silverman, R.; Wu, A. Y. (2002). "An efficient k-means clustering algorithm: Analysis and implementation" (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 24 (7): 881–892. doi:10.1109/TPAMI.2002.1017616. Retrieved 2009-04-24..

  • [28]

    ^Drake, Jonathan (2012). "Accelerated k-means with adaptive distance bounds" (PDF). The 5th NIPS Workshop on Optimization for Machine Learning, OPT2012..

  • [29]

    ^Dhillon, I. S.; Modha, D. M. (2001). "Concept decompositions for large sparse text data using clustering". Machine Learning. 42 (1): 143–175. doi:10.1023/a:1007612920971..

  • [30]

    ^Steinbach, M., Karypis, G., & Kumar, V. (2000, August). A comparison of document clustering techniques. In KDD workshop on text mining (Vol. 400, No. 1, pp. 525-526)..

  • [31]

    ^Pelleg, D., & Moore, A. W. (2000, June). X-means: Extending k-means with Efficient Estimation of the Number of Clusters. In ICML (Vol. 1)..

  • [32]

    ^Hamerly, G., & Elkan, C. (2004). Learning the k in k-means. Advances in neural information processing systems, 16, 281..

  • [33]

    ^Amorim, R.C.; Mirkin, B. (2012). "Minkowski Metric, Feature Weighting and Anomalous Cluster Initialisation in k-Means Clustering". Pattern Recognition. 45 (3): 1061–1075. doi:10.1016/j.patcog.2011.08.012..

  • [34]

    ^Amorim, R.C.; Hennig, C. (2015). "Recovering the number of clusters in data sets with noise features using feature rescaling factors". Information Sciences. 324: 126–145. arXiv:1602.06989. doi:10.1016/j.ins.2015.06.039..

  • [35]

    ^Sculley, David (2010). "Web-scale k-means clustering". Proceedings of the 19th international conference on World Wide Web. ACM. pp. 1177–1178. Retrieved 2016-12-21..

  • [36]

    ^Telgarsky, Matus. "Hartigan's Method: k-means Clustering without Voronoi" (PDF)..

  • [37]

    ^Kulis, Brian; Jordan, Michael I. (2012-06-26). Revisiting k-means: new algorithms via Bayesian nonparametrics (PDF). ICML. pp. 1131–1138. ISBN 9781450312851..

  • [38]

    ^Coates, Adam; Ng, Andrew Y. (2012). "Learning feature representations with k-means" (PDF). In G. Montavon, G. B. Orr, K.-R. Müller. Neural Networks: Tricks of the Trade. Springer.CS1 maint: Uses editors parameter (link).

  • [39]

    ^Csurka, Gabriella; Dance, Christopher C.; Fan, Lixin; Willamowski, Jutta; Bray, Cédric (2004). Visual categorization with bags of keypoints (PDF). ECCV Workshop on Statistical Learning in Computer Vision..

  • [40]

    ^Coates, Adam; Lee, Honglak; Ng, Andrew Y. (2011). An analysis of single-layer networks in unsupervised feature learning (PDF). International Conference on Artificial Intelligence and Statistics (AISTATS). Archived from the original (PDF) on 2013-05-10..

  • [41]

    ^Schwenker, Friedhelm; Kestler, Hans A.; Palm, Günther (2001). "Three learning phases for radial-basis-function networks". Neural Networks. 14 (4–5): 439–458. CiteSeerX 10.1.1.109.312. doi:10.1016/s0893-6080(01)00027-2..

  • [42]

    ^Lin, Dekang; Wu, Xiaoyun (2009). Phrase clustering for discriminative learning (PDF). Annual Meeting of the ACL and IJCNLP. pp. 1030–1038..

  • [43]

    ^Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 16.1. Gaussian Mixture Models and k-Means Clustering". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8..

  • [44]

    ^Aharon, Michal; Elad, Michael; Bruckstein, Alfred (2006). "K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation" (PDF). IEEE Transactions on Signal Processing. 54 (11): 4311. Bibcode:2006ITSP...54.4311A. doi:10.1109/TSP.2006.881199. Archived from the original (PDF) on 2013-06-20..

  • [45]

    ^H. Zha, C. Ding, M. Gu, X. He and H.D. Simon (Dec 2001). "Spectral Relaxation for k-means Clustering" (PDF). Neural Information Processing Systems Vol.14 (NIPS 2001): 1057–1064.CS1 maint: Uses authors parameter (link).

  • [46]

    ^Chris Ding and Xiaofeng He (July 2004). "K-means Clustering via Principal Component Analysis" (PDF). Proc. Of Int'l Conf. Machine Learning (ICML 2004): 225–232.CS1 maint: Uses authors parameter (link).

  • [47]

    ^Drineas, P.; A. Frieze; R. Kannan; S. Vempala; V. Vinay (2004). "Clustering large graphs via the singular value decomposition" (PDF). Machine Learning. 56 (1–3): 9–33. doi:10.1023/b:mach.0000033113.59016.96. Retrieved 2012-08-02..

  • [48]

    ^Cohen, M.; S. Elder; C. Musco; C. Musco; M. Persu (2014). "Dimensionality reduction for k-means clustering and low rank approximation (Appendix B)". arXiv:1410.6801 [cs.DS]..

  • [49]

    ^Little, M.A.; Jones, N.S. (2011). "Generalized Methods and Solvers for Piecewise Constant Signals: Part I" (PDF). Proceedings of the Royal Society A. 467 (2135): 3088–3114. Bibcode:2011RSPSA.467.3088L. doi:10.1098/rspa.2010.0671. PMC 3191861. PMID 22003312..

  • [50]

    ^Alon Vinnikov and Shai Shalev-Shwartz (2014). "K-means Recovers ICA Filters when Independent Components are Sparse" (PDF). Proc. Of Int'l Conf. Machine Learning (ICML 2014).CS1 maint: Uses authors parameter (link).

  • [51]

    ^Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52 (2): 341–378. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377..

阅读 245
版本记录

  • 暂无