并不使用层级结构。基于层次的算法的输入是一个n*n的相似度矩阵，期中n是用于聚类的数据对象的数量。另一方面，基于划分的算法既可以使用n*d的模式矩阵，期中n是表示有d维特征空间的n个对象，也可以使用相似度矩阵。值得注意的是相似度矩阵可以很容易的由模式矩阵导出，但是要从相似度矩阵中导出模式矩阵就要使用像多维定标（MDS）这样的定标方法。
最著名的基于层次的算法是单一连接和完全链接；最受欢迎也最简单的基于划分的算法是K-means。由于可用数据本身的性质决定基于划分的算法在模式识别中更加受欢迎，我们在这里主要讨论这类算法。K-means自从在不同的科学领域中由Steinhaus（1956）、Lloyd（1957年提出，1982年发表）、Ball和Hall（1965）以及MacQueen（1967）独立的发现以来，已经有了丰富而多样的历史。即使K-means距离它第一次提出已经过去了50多年，它仍然是聚类中最广泛使用的算法之一。易实现、简单、有效、经验上的成功是这个算法如此受欢迎的主要原因。下面，我们先总结一下K-means的发展历程，然后讨论数据聚类中的主要的成熟方法。 2.3. K-means算法
令X={xi}，i=1，...,n是要用来分成K个簇C={ck，k=2，...,K}的d维点集。K-means算法找到一个使得一个聚类中经验均值和点之间的平方误差最小。令μ
k
为ck的均值，类ck中μ
k
和点之间的平方误差定义为J?ck??Kxi?ck?xi?uk2。
K-means的目标是使得所有K个聚类中平方误差的和J?C????xi?ukk?1xi?ck2最
小。最小化这个目标函数是一个NP困难问题（即使K=2）（Drineas et al.,1999）。因此K-means是一个贪心算法，只能收敛于局部最优解，即使最近的研究表明当簇很好分开时K-means有很大的可能概率收敛于全局最优解（Meila，2006）。K-means从初始划分的K个聚类开始，并给簇分配模式以便减少平方误差。因为当簇数目K增加时平方误差总会减少（当K=n时，J（C）=0），只有当聚类数目是固定数量时才可以最小化J（C）。K-means算法的主要步骤如下（Jain and Dubes，1988）：
1.选择一个有K个簇的初始划分；重复步骤2和3直到每个聚类中的对象稳定。
2.通过将每个模式分配给各距离簇中心最近的簇产生一个新的划分。 3.计算新簇中心。
图4是一个有三类的2维数据集K-means算法的例子。
图4. K-means算法的例子。图（a）表示有三个簇的二维输入数据；图（b）表示了用作簇中心的三个种子点以及数据点的初始簇分配。图（c）和（d）表示簇标和簇中心的中间迭代。图（e）表示K-means收敛最后得到的聚类结果。
2.4. K-means的参数
K-means算法需要用户确定三个参数：类的数目K、类的初始化、距离尺度。其中最重要的参数是K。因为目前还没有准确的数学标准存在，可以选择已有的许多试探性求解（见Tibshirani et al.，2001）K的方法。一般来说，K-means在不同的K下会独立的运行，并产生不同的划分，对于领域专家来说最有意义的那种划分就会被选择。因为K-means只能收敛于局部最优解，不同的初始化会产生不同的聚类结果。一种寻找全局最优解的方法是在一个给定的K下，使用不同的初始划分多次运行K-means算法，然后选择平方误差最小的划分。
K-means一般会选择欧几里得距离作为距离尺度来计算点和簇中心之间的距离。因此K-means找到的是数据中球面和球体的簇。K-means利用马氏距离可以被用来寻找超椭球体的簇（Mao 和 Jain，1996），但是这需要更大量的计算
花费。一个K-means的变体使用板仓距离来处理在语音处理中的矢量量化问题（Linde et al.，1980）。L1距离被建议用来为K-means开发Bregman 距离族（Kashima et al.,2008.Banerjee et al.2004）。 2.5. K-means的扩展
基础的K-means算法已经被很多不同的方式扩充了。有些扩充使用额外的试探性方法处理簇尺寸最小化，合并和分离簇。在模式识别文献中的两个有名的K-means变体是ISODATA(Ball 和 Hall，1965)和FORGY（Forgy，1965）。在K-means中，每个数据点被分配到一个单一簇中（叫做硬分配）。由Dunn（1973）提出，并由Bezdek（1981）改进的模糊c-means，作为K-means的一个拓展，它的每个数据点可以是多个簇的成员（软分配），其中用成员值加以区分。一个好的可供使用的关于基于模糊的聚类综述是（Backer，1978）。在聚类之前，通过用分组数据的中心代替原来的数据可以加速K-means和模糊c-means（Eschrich et al.,2003）。下面概括K-means的其它重要的修正算法：Steinbach et al.(2000)提出了一种K-means的层次分裂版本，叫做二等分K-means，它每一步迭代划分数据为两个簇。在（Pelleg和Moore，1999）中，kd树被用来处理K-means的核心步骤，即有效的识别所有数据点中最近的簇中心。Bradlry et al.(1998)提出了K-means的一个快速可伸缩单次扫描版本，它不需要所有的数据同时适合内存。X-means（Pelleg和Moore，2000）可以通过优化比如AIC或BIC这样的准则自动化的找到K。在K-medoids（Kaufman和Rousseeuw，2005）中，由数据的中位数代替均值表示簇。核心K-means（Scholkopf et al.,1998）被提出来通过选择核心相似度函数用于发现任意形状的簇。值得注意的是所有这些拓展都要增加由用户确定的算法附加参数。 2.6. 聚类的主要方法
就像之前提到的一样，在很多不同的学科的文献中提出了数以千计的聚类算法。这使得回顾所有这些已经发表的方法变得非常困难。好在，聚类算法的主要差异是在目标函数的选择、概率生成模型和试探法三个方面。我们将简要回顾一些主要的方法。
簇可以被定义为在特征空间中由低密度区域分开的高密度区域。算法根据这个簇的定义直接搜索特征空间中连通的稠密区域。不同的算法使用不同的连通性定义。Jarvis-Patrick算法定义一对点之间的相似度为它们共享的邻近点的数量，临近点是指出现在某一点的一定半径区域内的点（Frank 和 Todeschini，1994）。Ester et al.(1996)提出了和Jarvis-Patrick算法相似的DBSCAN聚类算法。它通过使用Parzen窗方法估计密度，直接搜索连通的稠密区域。Jarvis-Patrick算法和DBSCAN的性能依赖于两个参数：距离角度的邻域尺寸和一个簇的邻域内包含的点的最小数量。另外，许多概率模型被开发用于数据聚类，即通过混合概率模型模拟密度函数。这些方法假设数据由一个混合分布生成，即每个簇被一个或多个混合分布的组合来描述（McLachlan和Basford，1987）。EM算法（Dempster et al.,1977）经常被用来推断混合模型的参数。包括潜在狄利克雷分布（LDA）（Bleiet al.2003）、弹球分布模型（Li和McCallum，2006）和无指导数据聚类图形模型（Welling et al.2005）在内的几个贝叶斯方法已经被开发来改进用于数据聚类的混合模型。
虽然基于密度的方法，尤其是无参数的基于密度的方法因为可以处理任意形状的簇的内在性质而很有吸引力，但是它们在处理高维数据时却有局限性。当数据是高维的，特征空间往往是高维的，这使得从低密度区域中区分高密度区域变得很难。子空间聚类算法通过找到嵌入在低维子空间的给定高维数据的簇来克服这个局限性。CLIQUE（Agrawal et al.,1998）是一个可伸缩的聚类算法，设计用于寻找数据中有高密度簇的子空间。因为它只在低维度子空间进行估计，CLIQUE并不会遇到高维问题。
图论聚类，有时也被叫做谱聚类，用一个加权的图代表数据点。连接两个节点之间的边由对间相似度加权。主要思想是：划分节点为A和B两个子集使得剪裁尺寸，也就是被分配给连接节点集A和B的边的权值的和是最小的。最初用于解决这个问题的算法是最小剪切算法，它经常导致两个簇有不平衡的尺寸。后来比率剪切算法采用了一种簇尺寸（一个簇中的数据点的数量）约束（Hagen和Kahng，1992）。另一种叫做规范化剪切的带有簇尺寸（簇的数据量或者单个簇内的边的权值和）的近似基于图剪切的有效聚类算法是由Shi和Malik（2000）第一次提出的。它的多级版本由Yu和Shi（2003）提出。Meila和Shi（2001）
提出了谱聚类的一种马尔科夫随机漫步观点并提出了可以处理任意簇数目的修正规范化剪切（MNCut）算法。Ng et al.(2001)提出了另一种谱聚类算法的变体，它从核心矩阵的规范化特征向量中导出一个新数据表示方法。拉普拉斯特征映射（Belkin和Niyogi，2002）是另一种谱聚类方法，它基于图的拉普拉斯算子导出数据表示方法。Hofmann 和Buhmann（1997）为聚类提出了一种确定性退火算法，它利用数据对象间的邻近衡量来表示数据。Pavan和Pelillo（2007）通过将最大支配集（Motzkin和Straus，1965）和簇相联系明确的表达了对间聚类问题，它是一个图中簇的一种连续产生方法。
有些聚类算法有一个信息理论公式。比如，Roberts et al.(2001)提出的最小熵方法假设数据是由一个混合模型生成的并且每个簇是使用一个半参数概率密度模式化的。参数通过最大化簇中数据点的无条件密度和有条件密度之间的KL散度来进行估计。这使得有条件和无条件的密度之间的重叠最小化，因此将簇分隔开。换句话说，这个公式是利用最小化所观察数据的预期熵的方法的结果。信息瓶颈方法（Tishby et al.，1999）被提出来作为速率失真理论和应用有损耗数据压缩观点的一般化。简单的说，给定两个随机变量的联合分布，信息瓶颈在最大化保留两个变量间的相互信息的前提下，压缩其中一个变量。（Slonim和Tishby,2000）展示了这种方法在文档聚类中的应用，其中的两个随机变量是单词和文档。单词通过使得和文档之间的信息得以最大化的保留来聚类，使用聚类后的单词，文档通过使得聚类后单词和聚类后文档之间的相互关系得到最大化的保留来聚类。
3. 用户的困境
尽管有如此大量的聚类算法，而且这些算法也在许多不同的领域成功应用，聚类仍然是一个困难的问题。这可以归因于簇定义本身的模糊性以及定义一个合适的相似度尺度和目标函数。
（Jain和Dubes，1998）强调以下聚类的主要挑战，这即使到今天来看依然是中肯的。
（a）什么是一个簇？ （b）应该使用哪些特征？