K-Means算法中K值的确定

K-Means算法中K值的确定 聚类算法在数据处理中有广泛的应用，K-Means算法是一种较为常用且有效的聚类算法。但它有一个缺点，在进行算法之前需要预先给出聚类的个数。因此，如何在K-Means算法中确定合适的K值成为该算法的一大问题。本文讨论了几种常用的确定K值的方法，并详细讨论了一种利用评价函数判断K值好坏的方法，之后在若干个数据集中进行了测试，取得了较好的效果。1.1 聚类算法的演变正所谓，物以类聚，人以群分。将可识别的物体进行分类一直以来都是符合人类的基本认知规律的。早在公元前三世纪的古希腊，分类学就已经作为一门科学盛行于当下，而作为其代表人物的亚里士多德不仅对五百余种不同的动植物进行了分类，还对五十余种动物进行了解剖，并首先指出鲸鱼是胎生的。我国著名医药学家李时珍外出至我国的各大名山大川考察，尝遍百草，将千余种植物分为五部，三十类。俄罗斯著名化学家门捷列夫更是首创了元素周期表，将化学元素依其质子数分门别类，并以此对一些尚未被发现的元素作出预言。可以看到的是，不论在人类的何种时期，将事物分门别类都是一个恒久的问题。在工业时代之前，通过人工的方法进行分类尚且是没有问题的。然而，在信息革命后的今天，我们若还是一味的依赖传统方法，就将难逃被时代淘汰的命运。因为信息时代所需要分门别类的，是海量的数据。而面对这样规模的数据，人工的方法将会有过大的消耗，再加上人类对于数据的认知是十分抽象的，缺乏直观的认识，因此其效果大打折扣。面对这些问题，聚类分析应运而生。聚类分析，又名群分析。它以相似性为基础，在没有鲜艳信息的前提下，将看似无序的研究样本分类成多个类簇。其原则是组内的相似性较高，而组间的相似性较低。它的起源便是上文所提到的分类学。在早期的分类学中，人们主要依靠经验和专业知识进行分类。纵观人类科技发展史，随着科技进程的不断推进，当原始的分类方法不足以满足我们对分类的需求，人们便将数学工具应用到分类学中，逐步形成了数值分类学、聚类分析等学科。聚类分析并不依赖于人类的直觉，而是通过算法的应用，将数据进行基于某种规则的客观分类。在数据规模增大到一定程度的时候，这种方法相较于传统方法就具有了不可比拟的优势。1.2 聚类算法的应用在生活中，聚类分析被广泛应用，譬如在推荐系统中，聚类分析就有着举足轻重的作用。当该系统作用时，我们需要识别出不同的客户群，即了解被推荐人可能还会想要购买什么商品。就网上书店而言，一个购买经济学原理的用户，还有可能会购买货币战争。而这样的用户可能被归为“经济学爱好者”这一客户群。那么，如果客户能够得到了正确的分类，则经系统推荐出的书目被售出的概率也将增大。因此，一个准确的聚类能够有效地提高商品的销量，具有很大的商业价值。在面对文本处理的问题中，我们可以运用聚类假设的原则，即相似度大的文档被分为同类文档，相似度小的文档被分为不同类文档。考虑到文本聚类不需要人工标注与训练过程，因此其具有比较高的自动化处理能力与灵活性。它在多文档自动文摘系统Newsblaster中作为其自然语言处理的预处理步骤。此外，在搜索引擎中，如果对搜索引擎的返回结果聚类，则可以缩小检索内容的范围，让用户更为精确地找到所需要的信息。而对于模式识别而言，聚类分析也显得颇为重要。在基于聚类的模式识别中，不论是图像识别，或是语音识别，首先要将图像转化为数据，亦即提取图像或是语音的特征值。在获取了特征值以后，图像或是语音便映射到了某个数据点。我们需要根据特征值对其进行聚类。从而在对某个陌生图像进行识别时，只需判断其特征值的分类便可完成识别。此外，聚类也可以应用于防垃圾邮件系统中。电子邮件是我们用于信息通讯的一个常用媒介。但是这个媒介时常会被利用作发送诸如广告，病毒，诈骗信息等垃圾邮件，打扰人们的正常使用。因此，在电子邮箱中，我们需要一个防垃圾邮件系统，用于鉴别“垃圾邮件”与“非垃圾邮件”。而对一个新的邮件进行分类，便可更好的判断该邮件是否属于不良邮件，以改善电子邮件用户的用户体验。聚类算法不仅应用广泛，其种类也是繁多的。依据其聚类原理可以分为基于划分的方法，基于层次的方法，基于密度的方法等等。而K-Means聚类算法就是一种十分经典的基于划分的方法。它的算法简单，聚类速度较快，但是有一个缺点：需要预先给出聚类数K的值。因此，本文的主要目的就是给出一个选择适合的K值的方法。在第二章中我们详细介绍了聚类算法原理，以及K-Means算法的过程，并讨论的一些古典的与新起的选取K值的方法。而第三章则重点讨论了一种评价函数选取K值的方法，并随后做了相应的数值试验以对其结果进行考量。第二章 浅谈聚类算法2.1 聚类算法的分类正如前文谈到的，数据聚类在数据分析中有着重要作用，并在多个领域诸如数据挖掘，机器学习和模式识别中都有着广泛的应用。它是通过将相似的对象分类成不同的子集类，最终使得不同类中的对象都拥有相近的属性。由于聚类的应用广泛，其数据来源也会十分广泛。这就导致了聚类算法可能需要处理多种多样的数据。而对于许多实际情况而言，数据不仅在维度上没有限制，其分布也未必有规律可循。这就意味着聚类算法对于属性不同的数据集要有一定的鲁棒性，以避免在对不同数据集进行聚类分析时效果差异太大。就目前聚类算法的发展情况来看，主要有以下几种方法，我们通过其主要原理做出了如下划分：1、基于网格的方法。这类算法把空间量化为有限个单元,然后所有的操作都在这个量化后的空间内进行。这类算法的执行时间独立于数据对象的数目,即只与单元数目有关 ,因此速度很快。这类算法包括:STING算法，WaveCluster算法，OptiGrid算法等。2、基于层次的方法。层次的方法是对给定数据对象集合进行层次的分解，通过对层次分解形成的分析，该类方法主要可分为自下而上凝聚的和自上而下分裂的两种。而在每一次的重复迭代过程中，不论是将相近的簇合并为一个新簇还是将一个内部差异较大的簇分裂为更小的簇，只要一个步骤一旦完成，它就不能被撤销。该类型算法包括：BIRCH算法，Chameleon算法，ROCK算法，CURE算法等。3、基于划分的方法。面对将n个给定的元组或者记录的数据集划分为K（Kn）个分组的问题，我们首先给出一种初始的划分方法，一个划分代表一个类簇。并用它将数据集进行初步划分。并在初步划分后通过重复迭代的方法逐步改变分组，优化结果直至无法改变聚合结果。该类算法要求在迭代的过程中，每次的聚合结果都能满足：每个分组至少包含一个对象并且每一个对象属于一个簇。该类算法的代表有：K-Means算法，PAM算法，STIRR算法，CLARA算法，CLARANS算法等 。4、基于密度的方法。这类算法主要是前人针对根据距离的划分方法提出的优化方法，她的处理原则是只要邻近区域的密度超过某个阙值,就继续聚类。该类算法的代表有：DBSCAN算法，DENCLUE算法，OPTICS算法，Incremental DBSCAN算法，FDBSCAN算法等。5、基于模型的方法。这类算法为每个类簇假定一个模型，然后寻找数据对给定模型求出其最佳拟合。该类算法主要有两类 : 神经网络和统计学方法方法。统计学方法包括COBWEB算法，CLASSIT算法，AutoClass算法。神经网络方法包含有竞争学习法和自组织特征映射法。2.2 K-Means算法的具体步骤K-Means算法作为聚类算法中较为经典的一种，是基于的是划分法聚类算法。划分方法通常是基于距离的。对于一次聚类，划分法会给出初始的分组，之后会不断对现有分组进行迭代，使得每一次迭代后得到的类簇较先前的分类结果好。同样的，K-Means算法也是根据数据对象与聚类中心的距离，将数据对象分配到与其距离最短的聚类之中，且最终将所有对象分配至K不同的聚类中。考虑到数据对象在分配到某个类簇之后，类簇的聚类中心将会发生改变。因此，数据对象每分配一次后，再次分配的结果会有所不同。通过多次迭代，聚类结果达到稳定时，我们认为该结果为K-Means聚类的最终结果。其主要步骤的细节如下：步骤 1：从样本集中选取K个样本作为初始的K个类簇中心；步骤 2：据最近邻法则，数据样本被分到与之最接近的类簇 ；步骤 3：计算新的类簇中心，即每个类簇中所有样本的均值；步骤 4：若类簇中心没有发生改变，算法终止，返回最终结果。否则返回步骤 2。该算法的计算复杂度的上限为,其中n为数据对象总数，k为聚类数，t为迭代次数。可以看到，在开始迭代之前，我们先要选取K个样本作为初始类簇的中心，也就是说在算法开始之前，需要先给定一个K值作为聚类个数。而K值的大小不仅关系到初始值的选取，也直接决定了最后聚类得到的类簇的个数。也就是说，如果不能找到一个较优的K值，聚类的效果将无法保证。那么该如何确定一个合适的K值，也就成了我们面临关键问题。2.3 K值选取的一些方法作为一种无监督算法，K-Means算法具有算法简单、收敛速度快的优点。但K-Means算法有一个缺点，那就是需要预先给定一个K值，而且该值确定的合理与否将直接影响到最终的聚类结果。而在现实中，算法所要处理的数据集是非常多样的。对于不同的数据集而言，其数据特性、维度、大小，都会有很大的差别。因此，适宜不同数据集的K值差距可能会非常大，而且并不存在一个普遍适用的K值。那么，我们应该如何选取一个合适的K值呢？最简单的确定K值的方法便是使用者凭借直观感觉与经验进行预定义。杨善林在2006年使用距离代价函数作为聚类有效性检验函数，并在理论上证明了的经验规则的合理性，其中为搜索域中的上限，N为数据集中的元素总数。然而该经验规则只提供了一个上限，在使用过程中若要找到更为合适的K值，则需要使用者有更为丰富的经验。但数据维数越高，使用者就越难对其有直观的认识。因此，这种经验性的方法很难满足大部分的需求。在聚类算法测试中，使用的数据通常是通过一些分布函数的随机生成器得到（常用的是均匀分布的随机生成器）。此时，聚类的最佳个数通常会等于随机生成器的个数。因此，该方法可以胜任数值试验中对聚类算法的的聚类效果的评估。虽然在一定条件下，我们也可以使用该方法选取适合的K值。但是，在大多数实际情况中，并不存在这样的一个生成器，数据分布也与生成函数有所不同。也就是说，该方法的使用条件太理想化，很难在实际条件中使用。此外，一些统计学方法也可以用于确定K值。这些方法也应用于概率聚类，且通常会假设数据遵循某种特定的分布。例如，对于服从高斯分布的数据集，通常会使用贝叶斯信息准则或是赤池信息量准则进行计算。而蒙特卡洛方法与虚无假设可以用于检验聚类结果，或是确定聚类个数。然而，考虑到概率聚类中的最大期望原理与K-Means聚类基于不同假设、模型与准则，使用概率聚类中的统计学方法来确定K值也显得并不那么严谨。更糟糕的是，对于实际数据符合某些分布的假设也很难得到证实。故该方法的实用性也大打折扣。另外，在最近的研究中一些启发式算法也被应用于确定K-Means算法中的K值。启发式算法是近年来兴起的一类算法，通常应用于最优化算法难以求解或求解代价很大的问题。由于在实际应用中，求解一个最优化问题可能是一个十分困难或十分缓慢的过程。而我们或许并不需要最优的结果，而只需要一个较优但花费较少的结果即可。因此启发式算法应运而生。而遗传算法作为一类较为经典的启发式算法。它参考了达尔文适者生存的进化论观点对数据进行处理。在自然选择中，有性生殖的生物体的遗传信息是由染色体携带的，且子代生物的遗传信息并非直接由父代生物直接遗传得到，而是从父代染色体中依据某种规律随机选取、组合得到的。由于染色体所控制的形状对于生物体的适应性将会有一定的影响，且适应性较低得生物体会有较大的概率被自然界所淘汰。因此，在数代的繁衍之后，生存下来的生物体就有较高的适应性。既然对于生物体而言是如此，那么若我们设计出一个类似的数据库自然界，则最终的选择结果将尽在掌握。首先我们将搜索空间上的每一个点都视为群落，并随机在搜索空间中选取若干的染色体，将其作为初始群落。其次我们需要有一个将搜索空间映射到实数域的一个函数，即适应度函数(fitness function)。该函数会对每一个染色体给出一个适应度。随后模拟群落的繁衍，适应度较高的染色体将有较大的几率会经过一系列的交叉、变异过程，生成下一代。而适应度较低的染色体将会有较大概率被“自然界”淘汰。数代繁衍后，便可得到适应度函数在搜索空间中的一个较好的局部最优值。需要特别指出的是对于K-Means算法而言，每一条染色体都对应一个K值，其聚类效果将会作为评价染色体适应度的标准。以此在若干代的繁衍之后，将得到一个聚类效果较好的K值。杨芳等在使用遗传算法实验K-Means聚类算法的K值选择中进行了相应的尝试，并取得了一定的成效。2.4 利用评价函数确定K值为了选取合适的K值，我们可以考虑使用一个评价函数f(K)对特定聚类数效果的好坏进行判断。首先，我们需要知道聚类的特点。大体而言，聚类是用来寻找数据分布中的不规律性以及数据分布中较为集中的区域。然而，并非每一个数据集中的区域都可以被定义为一个类簇。因为可能存在一个包含该区域的区域更适合作为一个类簇。因此，如果一个区域要被定义为一个类簇，重要的不仅仅在于分析其内部的分布，还在于分析它与其他的外部数据集间的依赖关系。特别的，我们定义K-Means算法中的畸变函数（distortion function）为类簇中每个点与其类簇中心的距离，即其中， 表示类簇j的畸变值， 表示类簇j的中心， 表示类簇j的元素个数，表示类簇j中第t个元素，表示类簇j中第t个元素与其中心的距离。据此，每一个类簇都可以通过其畸变函数 表示，且整个数据聚类所得结果的畸变函数则可由每个类的畸变函数求和得到。记为，其中K表示指定的聚类数目。据此，我们便可较好地判断一个数据空间中的某个特定区域是否适宜被视为一个类簇。另外，对于评价函数f(K)而言，其鲁棒性是相当重要的。考虑到f(K)是基于聚类算法所提出的，那么它的一个必不可少的性质便是在K值没有改变时，函数值的变化不大。然而，K-Means算法的一个固有特点就在于它的结果是随机的。因此，算法需要给出一个固定的结果作为评估函数的变量，这样它的表现便可以作为估计函数的一个参数。而置信K-Means算法，作为K-Means函数的一个变体就符合这些要求并且可以用于这项目。由于f(K)的角色是在于表示数据分布的趋势，因此需要与数据对象的总数N相互独立。对此我们假设聚类数K远小于数据对象总数N。那么，当K增加时，f(K)应该趋近于某些特定值。当K达到中间的某些值时，f(K)就应该表现出特定的行为，如取到函数的极大值点或是极小值点。而这样的K就有可能就是我们所要求的值。由于聚类分析是为了找到数据分布的无规律性，而当数据分布为均匀分布时，便不存在无规律性了。因此，具有均匀分布的数据集可以用于标定与检验聚类的结果。这个方法是被Tibshirani等人首先提出的。据此思路，我们首先生成一个与实际数据集维数相同的均匀分布数据。随后比较聚类算法应用于人工生成的数据集中的结果与其应用于实际数据集的结果，用Gap Statistic方法去评价聚类结果的有效性。但考虑到对生成的人工数据集进行聚类消耗较大，且Gap Statistic方法是面向所有聚类算法的评价方法，故在此并不去生成一个人工数据集，而是直接估计聚类算法在人工数据集中的效果，并用一个更有针对性的方法去估计聚类有效性。当K-Means算法应用于均匀分布且K值增加1后，聚类的结果通常会发生变化，而且其中心位置也会发生改变。在新的位置中，其新分割的尺寸大小与畸变值大体相近。根据D.T ，Pham等人在Incremental K-Means algorithm一文中提出的，当一个新的类簇插入一个均匀分布的聚类(K=1)时，其畸变值的减小值与原始的畸变值是成比例的，这个结论在K较小时也是正确的。依据上述结论，聚类数增大后的总体畸变值可以根据当前聚类的总体畸变值估算得到。在此我们使用评价函数f（K） （1） ，其中， （2） 。为聚类的总体畸变值，为数据集属性的个数（即数据的维度），为一个权重，(1)式中的是在整体数据服从