英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
k-means聚类算法的有效初始化方法的比较研究
M. Emre Celebia,uArr;, Hassan A. Kingravib, Patricio A. Velab
摘要
K-means无疑是最广泛使用的分区聚类算法。不幸的是，由于其渐变下降性质，该算法对聚类中心的初始放置非常敏感。已经提出了许多初始化方法来解决这个问题。在本文中，我们首先对这些方法进行综述，强调它们的计算效率。然后，我们使用各种性能标准，对八种常用的线性时间复杂度初始化方法在大量多样化的数据集上进行比较。最后，我们使用非参数统计检验分析实验结果，并为从业者提供建议。我们证明流行的初始化方法往往表现不佳，实际上这些方法有很强的替代性。
关键词：分区聚类平方和误差准则k-means聚类中心初始化
1.介绍
聚类，模式分组的无监督分类，是一个重要的任务，需要进行实验性的数据分析（Jain，Murty，＆Flynn，1999）。聚类的主要目标包括深入了解数据（检测异常，识别显着特征等），分类数据和压缩数据。聚类在包括人类学，生物学，医学，心理学，统计学，数学，工程学和计算机科学在内的各种科学学科中具有悠久而丰富的历史。因此，自20世纪50年代初期以来就提出了大量的聚类算法（Jain，2010）。聚类算法可以大致分为两组：分层和分区（Jain，2010）。分层算法递归地以自上而下（分裂）或自底向上（凝聚）的方式发现嵌套的聚类。相比之下，分区算法发现集群同时对数据进行划分，并且不强加分层结构。大多数分层算法在数据点数量方面具有二次或更高的复杂性（Jain et al.，1999），并且因此适用于大数据集，而分区算法通常具有较低的复杂性。给定一个数据集，即每个都有D个属性（分量）的N个点（向量），硬分区算法将X划分为K个穷举且互斥的集群这些算法通常通过优化标准函数来生成群集。最直观和经常使用的准则函数是由下式给出的平方和误差（SSE）：
（1）
（2）
可以近似为。可以看出，除了非常小的数据集（Kaufman＆Rousseeuw，1990）之外，全面列举全球最小值（1）的所有可能集群在计算上显然是禁止的。事实上，即使K = 2（Aloise，Deshpande，Hansen，＆Popat，2009）或D = 2（Mahajan，Nimbhorkar和Varadarajan，2012），这种非凸优化问题也被证明是NP难的。因此，各种启发式方法已经开发出来以提供解决这个问题的近似解决方案（Tarsitano，2003）。在这些启发式算法中，劳埃德算法（Lloyd，1982）通常被称为（批量）k均值算法，是最简单和最常用的算法。该算法以K个任意中心开始，通常从随机统一选择数据点。每个点被分配到最近的中心，然后每个中心被重新计算为分配给它的所有点的平均值。重复这两个步骤直到满足预定的终止标准。
k-means算法无疑是最广泛使用的分区聚类算法（Jain等，1999;Jain，2010）。其受欢迎程度可以归因于几个原因。首先，它在概念上简单易行。几乎每一个数据挖掘软件都包含了它的一个实现。其次，它是多功能的，即几乎算法的每个方面（初始化，距离函数，终止标准等）都可以修改。在过去的五年里，有数百种以各种方式扩展k-means的出版物证明了这一点。第三，它的时间复杂度在N，D和K中是线性的。由于这个原因，它可以用来初始化更昂贵的聚类算法，如期望最大化（Bradley＆Fayyad，1998），DBSCAN（Dash，Liu和Xu，2001）和谱聚类（Chen，Song，Bai，Lin，＆Chang，2011）。此外，在文献中还有许多连续的（Kanungo等，2002; Hamerly，2010）和平行的（Chen＆Chien，2010）加速技术。第四，它具有N，D和K线性的存储复杂性。此外，还有一些基于磁盘的变体不需要将所有点存储在内存中（Ordonez＆Omiecinski，2004）。第五，它保证以二次方的速度收敛（Selim＆Ismail，1984）（Bottou＆Bengio，1995）。最后，它对数据排序是不变的，即数据点的随机填充。
另一方面，k-means有几个显着的缺点。首先，它只能检测紧密的，超球形的团块，并且分离得很好。这可以通过使用更一般的距离函数来减轻，如Mahalanobis距离，它允许检测超椭球簇（Mao＆Jain，1996）。其次，由于它利用平方欧几里德距离，它对噪声和离群点很敏感，因为即使少数这样的点可以显着影响它们各自簇的平均值。这可以通过异常修剪来解决（Zhang＆Leung，2003）或使用更强大的距离函数，例如City-blocketh;L1THORN;距离。第三，由于其梯度下降性质，它往往收敛到标准函数的局部最小值（Selim＆Ismail，1984）。出于同样的原因，它对初始中心的选择非常敏感。不正确初始化的不利影响包括空集群，收敛速度较慢以及陷入局部最小极小值的可能性较高（Celebi，2011）。幸运的是，所有这些缺点，除了第一个可以通过使用自适应初始化方法（IM）来弥补。
在这项研究中，我们研究了一些为k-means算法开发的最流行的IM。我们的动机是三重的。首先，文献中提出了大量IMs，因此需要对这些方法进行回顾和比较的系统研究。其次，这些IM可用于初始化其他分区聚类算法，如模糊C均值及其变体和期望最大化。第三，这些IM中的大多数可独立于k-means用作独立聚类算法。
这项研究不同于以前的几个相似性研究（Pena，Lozano，＆Larranaga，1999; He，Lan，Tan，Sung，＆Low，2004）：（i）提供了对现有即时信息的更全面的概述 ，（ii）实验涉及更多的方法和更多样化的数据集合，（iii）除聚类有效性之外，计算效率被用作性能标准，并且（iv）更多地分析实验结果 彻底使用非参数统计测试。
本文的其余部分安排如下。第2部分介绍了k-means即时消息的调查。第3节介绍了实验装置。第4节给出了实验结果，第5节给出了结论。
2.k-means的初始化方法
在本节中，我们简要回顾一些常用的即时消息，重点是它们的时间复杂度（关于N）。在每个复杂等级中，方法按照时间顺序升序排列。
2.1 线性时间复杂度初始化方法
Forgy的方法（Forgy，1965）将每个点均匀地随机分配给K个簇中的一个。然后由这些初始聚类的质心给出中心。这种方法没有理论基础，因为这样的随机簇没有内部同质性（Anderberg，1973）。
Jancey的方法（Jancey，1966）为每个中心分配一个在数据空间内随机生成的合成点。除非数据集填补了空间，否则其中一些中心可能与任何一点都很远（Anderberg，1973），这可能导致形成空集群。
MacQueen（1967）提出了两种不同的方法。第一个是IBM SPSS Statistics（Noruscaron;is，2011）的Quick Cluster过程中的默认选项，它以X中的第一个K点作为中心。这种方法的明显缺点是它对数据排序的敏感性。第二种方法从数据点中随机选择中心。这种方法背后的基本原理是，随机选择可能会从密集区域挑选点，即可以成为中心的好候选点。然而，没有任何机制可以避免选择离群点或离得太近的点（Anderberg，1973）。这种多方法是初始化k均值的标准方法（Bradley＆Fayyad，1998）。应该指出的是，第二种方法通常被误认为是完全归于Forgy（1965）。
Ball和Hall的方法（Ball＆Hall，1967）将X的质心作为第一个中心，即X = 1 = NPN j = 1 xj。然后以任意顺序遍历这些点，如果它与先前选择的中心距离至少为T个单位，则以点为中心，直到获得K个中心。距离阈值T的目的是确保种子点良好分离。但是，很难为T决定合适的值。另外，该方法对数据排序很敏感。
简单群集寻找方法（Tou＆Gonzales，1974）与Ball和Hall的方法相同，不同之处在于X中的第一个点作为第一个中心。 SAS的FASTCLUS程序使用此方法（SAS Institute Inc.，2009）。
Spauml;th的方法（Spauml;th，1977）与Forgy方法类似，不同之处在于点以循环方式分配给聚类，即第j个（j2 {1,2，...，N}）点被分配到群集。与Forgy方法相反，这种方法对数据排序很敏感。
Maximin方法（Gonzalez，1985; Katsavounidis，Kuo和Zhang，1994）任意选择第一个中心c1，第i个（i2 {2,3，...，K}）中心ci被选择为与先前选择的中心具有最大的最小距离，即c1，c2，...，ci1。该方法最初是作为K-中心聚类问题的2近似而开发的。应当指出，在Katsavounidisetal.rsquo;svariant（Katsavounidisetal，1994）的矢量量化应用程序的驱动下，将最大的欧几里得范数作为第一个中央。
Al-Daoud的基于密度的方法（Al-Daoud＆Roberts，1996）首先将数据空间统一划分为M个不相交的超立方体。然后从超立方米m（m2 {1,2，...，M}）中随机选择个点，以获得总共K个中心（Nm是超立方体m中的点数）。这种方法有两个主要的缺点。首先，很难为M决定一个合适的值。其次，该方法的存储复杂度为，其中B是分配给每个属性的比特数。
Bradley和Fayyad的方法（Bradley＆Fayyad，1998）首先将数据集随机分成J个子集。这些子集使用k-means进行聚类，由MacQueen的第二种方法初始化，生成J组中间中心，每组中间中心都有K个点。这些中心集被组合成一个超集，然后通过k-means聚类J次，每次用不同的中心集进行初始化。然后将最少SSE的中心组成员作为最终中心。
Pizzuti，Talia和Vonella（1999）改进了Al-Daoud基于密度的方法，采用多分辨率网格方法。他们的方法从二维超立方体开始，并随着他们接收的点数增加而迭代地分解这些方法。一旦分裂阶段完成，中心从最密集的超立方体中选择。
k-means 方法（Arthur＆Vassilvitskii，2007）在MacQueen的第二种方法和maximin方法之间进行插值。它随机选择第一个中心，第i个（i2 {2,3，...，K}）中心选为x0 2 X，概率为mdxx0 2 PN j = 1 mddxj = 2，其中md（x） - 从点x到先前选择的中心的距离。该方法对MSSC问题产生H（logK）近似值。贪婪的k-means 方法在每轮中概率地选择log（K）中心，然后贪婪地选择最能减少SSE的中心。这种修改旨在避免选择两个彼此靠近的中心的情况。
PCA-Part方法（Su＆Dy，2007）采用基于PCA（主成分分析）的分层分层方法（Hotelling，1936）。从包含整个数据集的初始集群开始，该方法迭代地选择具有最大SSE的集群，并使用通过集群质心且与协方差的主特征向量的方向正交的超平面将其分成两个子集群矩阵。重复该过程直到获得K个群集。然后由这些集群的质心给出中心。Var-Part方法（Su＆Dy，2007）是PCA-Part的一种近似，其中要分割的聚类的协方差矩阵假定为对角线。在这种情况下，分裂超平面的方向与方差最大的坐标轴正交。
Lu等人的方法（Lu，Tang，Tang，＆Yang，2008）采用双相金字塔形方法。每个点的属性首先使用2Q级量化编码为整数，其中Q是分辨率参数。这些整数点被认为是在金字塔的第0级。在自下而上的阶段，从级别0开始，对级别为k（k2 {0,1，...}）的相邻数据点进行平均，以获得级别为k 1的加权点，直到获得至少20 K个点。最高级别的数据点使用用最大权重的K点初始化的k-means进行改进。在自顶向下阶段，从最高层开始，k 1层的中心被投影到k层，然后用于初始化第k层聚类。自顶向下阶段在达到等级0时终止。然后对这个级别的中心进行逆量化以获得最终的中心。这种方法的性能随着维度的增加而降低（Lu et al，2008）。
Onoda等人的方法（Onoda，Sakai和Yamada，2012）首先计算X的K独立分量（ICs）（Hyvauml;rinen，1999），然后选择第i个中心作为与第i个IC具有最小余弦距离的点。
2.2 线性时间复杂度初始化方法
Hartigan的方法（Hartigan和Wong，1979）首先根据它们到X的距离来排序这些点。第i个中心点与（1 （i-1）N / K ）。这种方法是对MacQueen的第一种方法的改进，因为它对数据排序不变，并且更可能产生良好分离的种子。这种方法的计算成本主要由排序的复杂性决定。
Al-Daoud的基于方差的方法（Al-Daoud，2005）首先对具有最大方差的属性进行排序，然后将它们按照相同的维度划分为K个组。然后选择这些中心作为与这些群体的中位数对应的点。请注意，此方法忽略除一个属性之外的所有属性，因此可能仅对其中可变性主要在一个维度上的数据集有效。这种变化主要集中在一个维度上。
Redmond和Heneghan的方法（Redmond＆Heneghan，2007）首先构建数据点的kd树来执行密度估计，然后使用密集最大化方法从密集叶片桶中选择K个中心。这种方法的计算成本主要由kd树构造的复杂性决定。
ROBIN（Robust INitialization）方法（Al Hasan，Chaoji，Salem，＆Zaki，2009）使用局部离群因子（LOF）（Breunig，Kriegel，Ng和Sander，2000）来避免选择离场点。在迭代中
全文共9905字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13236]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
