(完整版)X-means：一种针对聚类个数的K-means算法改进
X-means：一种针对聚类个数的K-means算法改进
摘要
尽管K-means很受欢迎，但是他有不可避免的三个缺点：1、它的计算规模是受限的。2、它的聚类个数K必须是由用户手动指定的。3、它的搜索是基于局部极小值的。在本文中，我们引入了前两种问题的解决办法，而针对最后一个问题，我们提出了一种局部补救的措施。根据先前有关算法改进的工作，我们引入了一种根据BIC（Bayesian Information Criterion）或者AIC（Akaike information criterion）得分机制而确定聚类个数的算法，本文的创新点包括：两种新的利用充分统计量的方式，还有一种有效地测试方法，这种方法在K-means算法中可以用来筛选最优的子集。通过这样的方式可以得到一种快速的、基于统计学的算法，这种算法可以实现输出聚类个数以及他们的参量值。实验表明，这种技术可以更科学的找出聚类个数K值，比利用不同的K值而重复使用K-means算法更快速。
1、介绍
K-means算法在处理量化数据中已经用了很长时间了，它的吸引力主要在于它很简单，并且算法是局部最小化收敛的。但是它有三点不可避免的缺点：首先，它在完成每次迭代的过程中要耗费大量的时间，并且它所能处理的数据量也是很少的。第二，聚类个数K值必须由用户自身来定义。第三，当限定了一个确定的K值时，K-means算法往往比一个动态K值的算法表现的更差。我们要提供针对这些问题的解决办法，通过嵌入树型的数据集以及将节点存储为充分统计变量的方式来大幅度提高算法的计算速度。确定中心的分析算法要考虑到泰森多边形边界的几何中心，并且在估计过程的任何地方都不能存在近似的方法。另外还有一种估计方法，“黑名单”，这个列表中将会包含那些需要在指定的区域内被考虑的图心。这种方法不仅在准确度上以及处理数据的规模上都表现的非常好，而这个快速算法在X-means 聚类算法当中充当了结构算法的作用，通过它可以很快的估计K值。这个算法在每次使用
K-means算法之后进行，来决定一个簇是否应该为了更好的适应这个数据集而被分开。决定的依据是BIC得分。在本文中，我们阐述了“黑名单”方法如何对现有的几何中心计算BIC 得分，并且这些几何中心所产生的子类花费不能比一个单纯的K-means聚类算法更高。更进一步的，我们还通过缓存状态信息以及估计是否需要重新计算的方法来改善估计方法。
我们已经用X-means算法进行了实验，验证了它的确比猜K值更加科学有效。X-means 算法可以在人造的或者是真实数据中表现的更好，通过BIC得分机制。它的运行速度也是比K-means更快的。
2、定义
我们首先描述简单的K-means算法应该考虑哪些因素。通过K-means可以把一定量的数据集分为K个数据子集，这K个数据子集分别围绕着K个聚类中心。这种算法保持着K个聚类中心不变，并且通过迭代不断调整这K个聚类中心。在第一次迭代开始之前，K个聚类中心都是随机选取的，算法当聚类中心不再变化的时候返回最佳的结果，在每一次迭代中，算法都要进行如下的动作：
1、对于每一个节点向量，找到距离它最近的聚类中心，归入此类。
2、重新评估每一个图心的位置，对于每一个图心，必须是簇的质心。
K-means聚类算法通过局部最小化每个向量到对应图心的距离来实现聚类。同时，它处理真实数据时是非常慢的。许多情况下，真实的数据不能直接用K-means进行聚类，而要经过二次抽样筛选之后再进行聚类。Ester曾经提出了一种可以从树形数据中获得平衡的抽样数据的方法。Ng和Han曾经提出了一种可以指导概率空间对输入向量的检索模拟模型。
Zhang则提出了一种基于充分统计学的树形模型。可以被用来异常识别以及快速计算。然而，这种聚类器是近似的，并且要依靠许多的近似值。
要注意虽然刚开始聚类的聚类中心是随便选取的，但是对于K-means算法来说，这K个聚类中心是实实在在确定了的。如果你选取了不科学的聚类中心，就有可能影响到最后的聚类结果以及算法的效率。Bradley和Fayyad讨论了通过二次抽样和平滑数据的方法来更加科学的选取聚类中心。
在本文的剩余部分，我们将会用u j来表示第J个质心，用i表示距离向量i最近的聚类质心，例如说，u i表示在迭代中距离i最近的聚类质心。D表示输入的数据节点，而D i表示所有距离u i最近的节点集。R为D中节点的个数，R i为D i中节点的个数。分布数量是M，高斯协方差矩阵为∑=diag(σ?σ)
3、K值的估计
到目前为止，我们所描述的算法是K-means聚类算法的相关步骤，K值是由用户确定的，我们现在要描述X-means算法如何确定K值，通过BIC得分的优劣，通过聚类算法我们不仅仅要得到一些比较合理的聚类中心还要得到一个合理的K值。首先，我们描述整个确定K
值的过程，不要太在意算法的细节。接下来，我们推导出适用于不同统计模型的测试集。再然后，我们回到高层的算法描述，显示算法是如何利用黑名单的思想将大量的数据存储在树形的数据集中。
3.1 模型检索
本质上，算法的运行过程主要是先给定一个聚类个数的下限，然后不停的用K-means
算法进行迭代，直到达到最好的BIC得分的结果，然后返回聚类结果。
迭代算法中主要包括以下动作：
X-means：
1、改变参数
2、改变结构
3、如果K大于最高限定的K值则返回结果，否则回到第一步
对参数的改变过程很简单，就是传统的K-means收敛的过程。
第二步中改变结构式算法的核心步骤，通过将一个大的聚类一分为二，然后决定新的质心应该出现的地方，我们要通过BIC得分来决定是否对聚类进行分割。
分裂观点1：第一个想法是先选择一个重心，然后再它附近再产生一个重心，然后评价是否两个重心的情况下聚类表现的更好，如果是则分割聚类，如果不是则返回上一步。这个过程需要在X-means算法聚类的整个过程中反复出现，直到返回最佳的聚类结果，算法的时间复杂度为O(K max)。
但是如果没有得到BIC得分的提高应该怎么办呢，我们就必须对每一个聚类中心都采取这种方式进行处理，所以每一次都需要调用一次K-means算法，也就是说我们在加一个聚类中心的时候需要运行很多次K-means，耗费了太多时间。
分裂观点2：将一个完整的簇分为两个部分，第二个想法用于SPLITLOOP系统，实现高斯混合模型识别。通过一些启发式的标准来简单的分割完整簇。分割他们时要调用K-means 算法并且计算分割后的成绩是否比分割之前更好，如果更好的话就返回分割之后的结果，这是一个比较大的改善，因为通过这种方法进行聚类的时间复杂度只有O(Log k)。不断的改善数据结构，直到X-means算法结束，但是这种思想的问题在于：什么样的启发机制用来分割聚类呢？还有图心应该拥有多大的规模呢？是图心决定了图结构的变化吗？如果只有一个或者是两个簇需要被分割，其他都不需要的话这种算法仍然是科学的吗？
我们的解决办法同时考虑了想法一和想法二的优点，同时还避免了他们的缺点，并且我
们的解决办法可以在很短时间内实现。我们将通过一个例子来解释。
图1展示了拥有三个图心的一个稳定的K-means聚类。每一个图心所拥有的区域边界也在图中展示出来了，对这个图的结构改进的过程如下：首先将每一个簇分为两个孩子簇（图2）。他们是被距离质心相反方向的两个向量的连线分割开来的。然后对于每一个父亲簇都运行一次K=2的K-means聚类算法，两个孩子类都要与对方争夺父亲类的聚类区域。图3表示了三个簇分别的分为两个孩子类的过程。图4表示所有的簇都已经分为了两个孩子类。
在这个时候，模型的测试机制会对每一对子类进行测试，测试内容包括：两个子类的建模过程是否有证据支撑？还有两个子类是否是由父类平均分配的。下一节我们会涉及如何用这样的测试集来测试K-means。根据测试出的结果，删除不符合标准的父亲类以及他们的后代，只有通过了这个过程的父亲类以及他们的孩子类才能留存下来。另外一方面，没有被现有的图心描述好到的空间将会在增加图心的过程中获得更多的关注。图5显示了图4经过这种处理之后的情况。
因此我们的搜索空间覆盖了所有的2k种可能的分割设置，并且每个区域的分割是由BIC 得分来确定的。与上述的想法1以及想法2比较，这种思路可以使得我们自动选择我们的聚类个数的增加量时非常少还是非常多。通过实际操作我们发现，K-means聚类运行两个聚类个数的时候是对局部最小化准则最不敏感的。
我们在最高限制K值下面将会不断的进行参数改善以及框架改善来得到一个更加科学的K值。
3.2 BIC得分
假设我们已经有了一个数据集D以及一些可供选择的模型M j，不同的模型对应了不同的K值。
我们如何才能选择最好的K值呢？我们将要用到后验概率来给模型进行打分。我们的所有模型都被K-means算法设定。为了按照统一的标准来设定后验概率，我们使用了以下公式：
在这个公式当中l j(D)表示数据针对于第j个模型的对数似然函数，并且取极大似然函数值，p j是模型M j中的参数数量，这个也被叫做Schwarz标准。
这些变化之后的极大似然函数估计要在同一个高斯假设下：
节点概率为：
节点的对数似然函数为
对于n属于1到K中间的数值时，只关注D n数据集中属于n个图心的点，并且插入最大似然函数的估计值。
参数P j就是就是简单的的鞥与K-1个类别的概率、M.K个累心的坐标以及方差的估计值。为了把这一个图心的公式延伸到所有图心上，我们设定节点的似然函数为节点对于所有图心的相对似然函数值，并且将R替代为所有列入考虑的节点向量。
我们在X-means确定最好的模型时全局的使用BIC公式，而局部的使用图心分割测试。
3.3加速
到目前为止，X-means可以用在之前的小型数据上，但是我们都忽略了X-means聚类算法的主要特点，那就是它可以使用在大型数据的分析当中。
对K-means算法的加速：我们以一个简单的K-means算法迭代开始，任务是最终确定哪一个节点属于哪一个质心，通过这种迭代，我们可以计算出所有的质心，并且确定属于节点都是属于哪一个给定的质心，同时确定质心的确定位置。得出结果之后，我们立刻就会发现，对于一个节点数据集的质心分配与对于一个单独的节点的中心分配过程是一样的，因为我们又足够的数据量作为支撑。显然，这样做可以节省很多的计算资源，所需要占用的资源往往不比证明一个点的归属问题多多少。既然kd-tree结构强加了一个分层的数据结构给数据，那么我们就可以很容易的计算它的节点的统计数据在建立他们的时候，对这些节点做一个局部的自然选择。每一个kd-tree代表一个点集。这个树形结构同样也有边界，即一个可以包括数据集中所有点的矩形。另外，这种树形结构有两个指针向量，向量表示每一个父亲节点都被分为了两个子节点。
设置一个计数器来存储每一个质心拥有多少个节点，现在我们来展示这种计数器如何只扫描一遍树形结构就能够统计到所有的图心的数据。统计的过程是一个递归的过程，把每个图心所拥有的点视作参数。它的任务就是更新节点计数器中点的值都到达一个适当的大小。在它递归返回之后，可能会由计数器产生新的位置信息。这个过程也包括根据之前提到的边界框将不可能拥有任何点的图心剔除出去，也就是在“黑名单”中出现的节点。这个过程的完整描述在Pelleg和Moore的论文中有体现。有一点要特别注意：在收缩了黑名单之后，这个过程要重新考虑现有节点的孩子节点。图心的计数器通过这样的方式增长。这种工作通常在较高级的树形结构中实现，但是清除工作往往在整个树形结构中实现。
加速结构改善过程：这个过程就是在K-means迭代过程中改变图心位置的过程。我们现在运用同样的过程来实现结构改善的过程。之前的方法是，我们对于每一个泰森多边形下的区域分为两块相同大小的区域。并首先列出父亲图心的列表，然后将其作为这个过程的输入变量。与全局迭代过程不同的地方在于当图心减少为只有一个单一图心的时候，算法所进行的动作。如果出现了这种情况，那就表明数据集中的所有的点都是可以被归纳为一个图心所包括的点。这个时候我们只要在它的孩子图心之间进行分割就可以了。为了达到这一目标，我们将这个图心分为两个孩子图心，然后评价是否应当对之前的结构进行分割。在对整个的树形结构进行扫描之后，（有可能删掉了很多的节点），子图心的计数器已经得到了一个最终的统计值，而且新的图心的位置也已经确定了，继而我们可以进行下一次迭代，直到所有的图心已经被处理完成。
额外的加速：在我哦们进行上述迭代的过程中，那些没有被考虑的空间区域往往为定义为活动的，那些已经被图心包括的区域被标记为静止的。我们可以将这种分析模式通过将它的先前迭代的统计状态作为缓存数据的方式来准换为一种更进一步的改进加速，考虑到两个图心的边界（这两个图心对数据集中的所有节点都有可能包括）。虽然我们必须遍历属性结构来更新我们计数器中的数值，但是我们没有理由在下一次迭代中再进行一遍这个动作，因为图心根本就没有移动过，也没有任何新加入的图心占用任何一个已经分配给图心的节点。因此我们可以记录下图心节点的数量然后进行连续迭代，而不用每次都对数据的树形结构进行一次遍历。
为了能够快速比较两个图心位置的优劣，我们使用一个写操作来实现：一旦数据结构不
允许在数据形成之后改变图心的位置，一旦图心的位置改变了，那么一个新的元素就必须插入进来，并且这个插入的元素有特别的识别标识。这个方法仅仅在两个图心进行比较的时候会用到。显然，因为旧的图心再也不会用到了，所以也没有什么继续存储他们的必要了。这就涉及到我们要建立一个原始的M.K存储器配上一个哈希表来快速寻找响应的标签。这个想法的更进一步的扩展可以把这种存储方式利用在图心的孩子节点上。这些节点将会变为僵尸状态而不是被删除。又由于他们的标识符是不会变的，所以说缓冲区存储的数据就是最后一次迭代完成之后的数据。
5、结论
本文中展现了一种新型的K-means算法来选择更加科学的数据分类模型。通过适应和扩展来提高K-means，用这个算法可以免除用户用不同的K值来测试哪个结果更加科学，
X-means算法只需要运行一次。它使用了统计学的标准来最大化样本的最大似然函数。是化验结果表明，本算法比K-means算法更快更好。
BIC评分标准作为分割标准并不是唯一的。虽然我们使用BIC在我们的算法当中有很好的表现，但是像AIC或者是MDL这种评价算法也是非常有用的。在以后的工作中我们有希望将这些算法合并起来进行评分。
另外一个BIC的应用延伸为：在一个自由高斯EM算法当中指挥模型检索。这部分的工作正在进行当中，大家可以找别的方法来指导模型检索，也可以加上本文中提到的思想。
使用我们的快速算法，可以在几个小时的时间内实现对百万的数据点，成白上千个类别的分析，因此，我们可以用这个方法来处理天体物理学方面的数据，而这些数据在之前我们是处理不了这么大规模的数据的。像上述提到的一样，我们的方法主要是为了帮助人们分析这些大规模的数据。
最后，我们需要考虑数据的维度，这篇论文证明X-means算法可以实现最多四维数据的分析，虽然一些更简单的算法可以实现最多七维的数据。但是七维的数据在我们对实际问题的分析当中是足够的吗？通过以下两种理由，我们可以得出一个肯定的答案。
首先，许多科学实验需要分析的数据往往都是大量的但是低维的三个银行业，只是要求算法有一定的计算速度。银河系、空间颜色以及蛋白质胶体聚类往往只有三维的数据，因此我们的算法可以用在这些科学问题的研究上。
第二，一些高维的数据通常都可以被一些低维的簇所代表，比如说贝叶斯节点网络。X-means算法可以作为分析这些复杂数据的体系中的一部分而存在。
聚类分析K-means算法综述
聚类分析K-means算法综述 摘要：介绍K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。 关键词：K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势 算法概述 K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含n个数据对象的数据库，输出满足方差最小标准的k个聚类。 评定标准：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。 解释：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。 k-means 算法基本步骤 （1）从n个数据对象任意选择k 个对象作为初始聚类中心 （2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分 （3）重新计算每个（有变化）聚类的均值（中心对象） （4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2） 形式化描述 输入：数据集D，划分簇的个数k 输出：k个簇的集合 （1）从数据集D中任意选择k个对象作为初始簇的中心； （2）Repeat （3）For数据集D中每个对象P do （4）计算对象P到k个簇中心的距离 （5）将对象P指派到与其最近（距离最短）的簇；
（6）End For （7）计算每个簇中对象的均值，作为新的簇的中心； （8）Until k个簇的簇中心不再发生变化 对算法已有优化方法的分析 (1)K-means算法中聚类个数K需要预先给定 这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K 值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标：V(k km) = Intra(k) + Inter(k) / Inter(k max)，其中k max是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是：对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。 (2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解 不同的初始值，结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效果的不稳定，并且，K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值，只有一个属于全局最小，由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过迭代运算，目标函数常常达到局部最小，得不到全局最小。对于这个问题的解决，许多算法采用遗传算法(GA)，例如文献中采用遗传算法GA进行初始化，以内部聚类准则作为评价指标。 (3)从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时,算法的时间开销是非常大 所以需要对算法的时间复杂度进行分析，改进提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的候选集，而在文献中，使用的K-meanS算法是对样本数据进行聚类。无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。
k-means聚类算法的研究全解
k-means聚类算法的研究 1．k-means算法简介 1.1 k-means算法描述 给定n个对象的数据集D和要生成的簇数目k，划分算法将对象组织划分为k个簇（k<=n），这些簇的形成旨在优化一个目标准则。例如，基于距离的差异性函数，使得根据数据集的属性，在同一个簇中的对象是“相似的”，而不同簇中的对象是“相异的”。划分聚类算法需要预先指定簇数目或簇中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数收敛时，得到最终聚类结果。这类方法分为基于质心的（Centroid-based）划分方法和基于中心的（Medoid-based）划分方法，而基于质心的划分方法是研究最多的算法，其中k-means算法是最具代表和知名的。 k-means算法是1967年由MacQueen首次提出的一种经典算法，经常用于数据挖掘和模式识别中，是一种无监督式的学习算法，其使用目的是对几何进行等价类的划分，即对一组具有相同数据结构的记录按某种分类准则进行分类，以获取若干个同类记录集。k-means聚类是近年来数据挖掘学科的一个研究热点和重点，这主要是因为它广泛应用于地球科学、信息技术、决策科学、医学、行为学和商业智能等领域。迄今为止，很多聚类任务都选择该算法。k-means算法是应用最为广泛的聚类算法。该算法以类中各样本的加权均值（成为质心）代表该类，只用于数字属性数据的聚类，算法有很清晰的几何和统计意义，但抗干扰性较差。通常以各种样本与其质心欧几里德距离总和作为目标函数，也可将目标函数修改为各类中任意两点间欧几里德距离总和，这样既考虑了类的分散度也考虑了类的紧致度。k-means算法是聚类分析中基于原型的划分聚类的应用算法。如果将目标函数看成分布归一化混合模型的似然率对数，k-means算法就可以看成概率模型算法的推广。 k-means算法基本思想： （1）随机的选K个点作为聚类中心； （2）划分剩余的点； （3）迭代过程需要一个收敛准则，此次采用平均误差准则。 （4）求质心（作为中心）； （5）不断求质心，直到不再发生变化时，就得到最终的聚类结果。 k-means聚类算法是一种广泛应用的聚类算法，计算速度快，资源消耗少，但是k-means算法与初始选择有关系，初始聚类中心选择的随机性决定了算法的有效性和聚
利用K-Means聚类进行航空公司客户价值分析
利用K-Means聚类进行航空公司客户价值分析 1.背景与挖掘目标 1.1背景航空公司业务竞争激烈，从 产品中心转化为客户中心。针对不同类型客户，进行精准营 销，实现利润最大化。建立客户价值评估模型，进行客户分 类，是解决问题的办法 1.2挖掘目标借助航空公司客户数据， 对客户进行分类。对不同的客户类别进行特征分析，比较不 同类客户的客户价值对不同价值的客户类别提供个性化服 务，制定相应的营销策略。详情数据见数据集内容中的 air_data.csv和客户信息属性说明 2.分析方法与过程 2.1分析方法首先，明确目标是客户价值识别。识别客户价值，应用 最广泛的模型是三个指标（消费时间间隔（Recency）,消费频率（Frequency）,消费金额（Monetary））以上指标简称RFM 模型，作用是识别高价值的客户消费金额，一般表示一段时 间内，消费的总额。但是，因为航空票价收到距离和舱位等 级的影响，同样金额对航空公司价值不同。因此，需要修改 指标。选定变量，舱位因素=舱位所对应的折扣系数的平均 值=C，距离因素=一定时间内积累的飞行里程=M。再考虑到，航空公司的会员系统，用户的入会时间长短能在一定程度上 影响客户价值，所以增加指标L=入会时间长度=客户关系长度总共确定了五个指标，消费时间间隔R，客户关系长度L，消费频率F，飞行里程M和折扣系数的平均值C以上指标，
作为航空公司识别客户价值指标，记为LRFMC模型如果采用传统的RFM模型，如下图。它是依据，各个属性的平均 值进行划分，但是，细分的客户群太多，精准营销的成本太 高。 综上，这次案例，采用聚类的办法进行识别客户价值，以LRFMC模型为基础本案例，总体流程如下图 2.2挖掘步骤从航空公司，选择性抽取与新增数据抽取，形 成历史数据和增量数据对步骤一的两个数据，进行数据探索 性分析和预处理，主要有缺失值与异常值的分析处理，属性 规约、清洗和变换利用步骤2中的已处理数据作为建模数据，基于旅客价值的LRFMC模型进行客户分群，对各个客户群 再进行特征分析，识别有价值客户。针对模型结果得到不同 价值的客户，采用不同的营销手段，指定定制化的营销服务，或者针对性的优惠与关怀。（重点维护老客户） 2.3数据抽取选取，2014-03-31为结束时间，选取宽度为两年的时间段， 作为观测窗口，抽取观测窗口内所有客户的详细数据，形成 历史数据对于后续新增的客户信息，采用目前的时间作为重 点，形成新增数据 2.4探索性分析本案例的探索分析，主要 对数据进行缺失值和异常值分析。发现，存在票价为控制， 折扣率为0，飞行公里数为0。票价为空值，可能是不存在 飞行记录，其他空值可能是，飞机票来自于积分兑换等渠道，查找每列属性观测值中空值的个数、最大值、最小值的代码
第9章rapidminer_k_means聚类.辨别分析v1
第9章K-Means 聚类、辨别分析 9.1理解聚类分析 餐饮企业经常会碰到这样的问题： 1）如何通过餐饮客户消费行为的测量，进一步评判餐饮客户的价值和对餐饮客户进行细分，找到有价值的客户群和需关注的客户群？ 2）如何合理对菜品进行分析，以便区分哪些菜品畅销毛利又高，哪些菜品滞销毛利又低？ 餐饮企业遇到的这些问题，可以通过聚类分析解决。 9.1.1常用聚类分析算法 与分类不同，聚类分析是在没有给定划分类别的情况下，根据数据相似度进行样本分组的一种方法。与分类模型需要使用有类标记样本构成的训练数据不同，聚类模型可以建立在无类标记的数据上，是一种非监督的学习算法。聚类的输入是一组未被标记的样本，聚类根据数据自身的距离或相似度将他们划分为若干组，划分的原则是组样本最小化而组间（外部）距离最大化，如图9-1所示。 图9-1 聚类分析建模原理 常用聚类方法见表9-1。 表9-1常用聚类方法 类别包括的主要算法
常用聚类算法见图9-2。 表9-2常用聚类分析算法 9.1.2K-Means聚类算法 K-Means算法是典型的基于距离的非层次聚类算法，在最小化误差函数的基础上将数据划分为预定的类数K，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。 1.算法过程 1）从N个样本数据中随机选取K个对象作为初始的聚类中心； 2）分别计算每个样本到各个聚类中心的距离，将对象分配到距离最近的聚类中； 3）所有对象分配完成后，重新计算K个聚类的中心； 4）与前一次计算得到的K个聚类中心比较，如果聚类中心发生变化，转2)，否则转 5)； 5）当质心不发生变化时停止并输出聚类结果。 聚类的结果可能依赖于初始聚类中心的随机选择，可能使得结果严重偏离全局最优分类。实践中，为了得到较好的结果，通常以不同的初始聚类中心，多次运行K-Means算法。在所有对象分配完成后，重新计算K个聚类的中心时，对于连续数据，聚类中心取该簇的均值，但是当样本的某些属性是分类变量时，均值可能无定义，可以使用K-众数方
matlab实现Kmeans聚类算法
matlab实现Kmeans聚类算法 1.简介： Kmeans和应用于混合高斯模型的受限EM算法是一致的。高斯混合模型广泛用于数据挖掘、模式识别、机器学习、统计分析。Kmeans 的迭代步骤可以看成E步和M步，E：固定参数类别中心向量重新标记样本，M：固定均值只考虑（估计）了均值，而没有估计类别的方差，所以聚类的结构比较适合于特征协方差相等的类别。 Kmeans在某种程度也可以看成Meanshitf的特殊版本，Meanshift 是所以Meanshift可以用于寻找数据的多个模态（类别），利用的是梯度上升法。在06年的一篇CVPR文章上，证明了Meanshift方法是牛顿拉夫逊算法的变种。Kmeans和EM算法相似是指混合密度的形式已知（参数形式已知）情况下，利用迭代方法，在参数空间中搜索解。而Kmeans和Meanshift相似是指都是一种概率密度梯度估计的方法，不过是Kmean选用的是特殊的核函数（uniform kernel），而与混合概率密度形式是否已知无关，是一种梯度求解方式。 k-means是一种聚类算法，这种算法是依赖于点的邻域来决定哪些点应该分在点，也可以对高维的空间（3维，4维，等等）的点进行聚类，任意高维的空间都可以。 上图中的彩色部分是一些二维空间点。上图中已经把这些点分组了，并使用了不同的颜色对各组进行了标记。这就是聚类算法要做的事情。 这个算法的输入是： 1：点的数据（这里并不一定指的是坐标，其实可以说是向量）
2：K，聚类中心的个数（即要把这一堆数据分成几组） 所以，在处理之前，你先要决定将要把这一堆数据分成几组，即聚成几类。但并不是在所有情况下，你都事先就能知道需要把数据聚成几类的。意味着使用k-means就不能处理这种情况，下文中会有讲解。 把相应的输入数据，传入k-means算法后，当k-means算法运行完后，该算法的输出是： 1：标签（每一个点都有一个标签，因为最终任何一个点，总会被分到某个类，类的id号就是标签） 2：每个类的中心点。 标签，是表示某个点是被分到哪个类了。例如，在上图中，实际上有4中“标签”，每个“标签”使用不同的颜色来表示。所有黄色点我们可以用标签以看出，有3个类离的比较远，有两个类离得比较近，几乎要混合在一起了。 当然，数据集不一定是坐标，假如你要对彩色图像进行聚类，那么你的向量就可以是(b,g,r)，如果使用的是hsv颜色空间，那还可以使用(h,s,v),当然肯定可以有不同的组合例如(b*b,g*r,r*b) ，(h*b,s*g,v*v)等等。 在本文中，初始的类的中心点是随机产生的。如上图的红色点所示，是本文随机产生的初始点。注意观察那两个离得比较近的类，它们几乎要混合在一起，看看算法是如何将它们分开的。 类的初始中心点是随机产生的。算法会不断迭代来矫正这些中心点，并最终得到比较靠5个中心点的距离,选出一个距离最小的(例如该点与第2个中心点的距离是5个距离中最小的),那么该点就归属于该类.上图是点的归类结果示意图. 经过步骤3后,每一个中心center(i)点都有它的”管辖范围”,由于这个中心点不一定是这个管辖范围的真正中心点,所以要重新计算中心点,计算的方法有很多种,最简单的一种是,直接计算该管辖范围内所有点的均值,做为心的中心点new_center(i). 如果重新计算的中心点new_center(i)与原来的中心点center(i)的距离大于一定的阈值（该阈值可以设定），那么认为算法尚未收敛，使用new_center(i)代替center(i)（如图，中心点从红色点
利用K-Means聚类进行航空公司客户价值分析.doc
利用 K-Means 聚类进行航空公司客户价值分析 1.背景与挖掘目标 1.1 背景航空公司业务竞争激烈，从 产品中心转化为客户中心。针对不同类型客户，进行精准营 销，实现利润最大化。建立客户价值评估模型，进行客户分 类，是解决问题的办法 1.2 挖掘目标借助航空公司客户数据，对客户进行分类。对不同的客户类别进行特征分析，比较不 同类客户的客户价值对不同价值的客户类别提供个性化服 务，制定相应的营销策略。详情数据见数据集内容中的 air_data.csv 和客户信息属性说明 2.分析方法与过程 2.1 分析方法首先，明确目标是客户价值识别。识别客户价值，应用 最广泛的模型是三个指标（消费时间间隔（Recency） ,消费 频率（ Frequency）,消费金额（ Monetary ））以上指标简称RFM 模型，作用是识别高价值的客户消费金额，一般表示一段时 间内，消费的总额。但是，因为航空票价收到距离和舱位等 级的影响，同样金额对航空公司价值不同。因此，需要修改 指标。选定变量，舱位因素=舱位所对应的折扣系数的平均 值=C，距离因素 =一定时间内积累的飞行里程 =M 。再考虑到，航空公司的会员系统，用户的入会时间长短能在一定程度上 影响客户价值，所以增加指标 L= 入会时间长度 =客户关系长度总共确定了五个指标，消费时间间隔 R，客户关系长度 L ，消费频率 F，飞行里程 M 和折扣系数的平均值 C 以上指标，
作为航空公司识别客户价值指标，记为LRFMC 模型如果采用传统的 RFM 模型，如下图。它是依据，各个属性的平均 值进行划分，但是，细分的客户群太多，精准营销的成本太 高。 综上，这次案例，采用聚类的办法进行识别客户价值，以LRFMC 模型为基础本案例，总体流程如下图 2.2 挖掘步骤从航空公司，选择性抽取与新增数据抽取，形 成历史数据和增量数据对步骤一的两个数据，进行数据探索 性分析和预处理，主要有缺失值与异常值的分析处理，属性 规约、清洗和变换利用步骤 2 中的已处理数据作为建模数据， 基于旅客价值的 LRFMC 模型进行客户分群，对各个客户群再 进行特征分析，识别有价值客户。针对模型结果得到不同 价值的客户，采用不同的营销手段，指定定制化的营销服务，或者针对性的优惠与关怀。（重点维护老客户） 2.3 数据抽取选取， 2014-03-31 为结束时间，选取宽度为两年的时间段，作为观测窗口，抽取观测窗口内所有客户的详细数据，形成 历史数据对于后续新增的客户信息，采用目前的时间作为重 点，形成新增数据 2.4 探索性分析本案例的探索分析，主要对 数据进行缺失值和异常值分析。发现，存在票价为控制，折扣 率为 0，飞行公里数为 0。票价为空值，可能是不存在飞行记录，其他空值可能是，飞机票来自于积分兑换等渠道，查找 每列属性观测值中空值的个数、最大值、最小值的代码
K-means文本聚类算法
最大距离法选取初始簇中心的K-means文本聚类算法的研究 的评论 背景 随着计算机技术和网络技术的飞速发展，人们的生活方式产生了极大的改变。计算机从一个有几个房子大小的巨无霸，已经变成了小巧的笔记本。网络设备也已经从PC端走向移动端。越来越丰富的网络设备，让人们能在网络里畅游，网络对于人们来说触手可及，同时也产生了巨大的数据流量。人们如何从海量的数据中找到有用的信息，成为了现在计算机学科的研究热点。聚类是数据挖掘中重要的一支。由于聚类具有无需先验知识的优势，可以根据数据自然分部而获取知识。聚类成为数据挖掘领域一个非常活跃的领域，而且得到了广泛的应用。聚类就是把一个数据集合分成几个簇，在同一个簇里，数据相关性最高，但是在2个不同的簇里，数据相关性最低。K-means聚类算法主要针对处理大数据集时，处理快速简单，并且算法具有高效性和可伸缩性。但是，K-means聚类算法随机的选择初始簇中心会导致以下缺点：（1）得到的聚类结果中容易出现局部最优，而不是全局最优；（2）聚类结果不具有稳定性，很大程度上依赖于初始簇中心；（3）聚类过程中的迭代次数增加使聚类过程中的总耗时增加。 传统的k-means聚类算法 传统的聚类算法思想：首先从N个数据对象集合中随机选择k个对象，然后计算剩余的N-k个对象与k个对象的距离（相似度），与k个对象中哪个对象的距离最小，就把分给那个对象；然后在计算每个簇中的簇中心，即是每个簇中对象的均值；不断重复这一过程步骤，直到标准测度函数E开始收敛为止。 K-means算法描述如下： 输入：迭代终止条件ε，最大的迭代次数为max，簇的总数目是k，样本集有N个数据对象。 输出：满足迭代终止条件的k个簇和迭代次数s。 随机初始化k个簇中心： 对每个数据对象，分别计算该对象与k个簇中心均值的距离，并选择距离最小的簇将该对象加个到该簇里； 重新计算k个簇的中心，利用函数E计算出此时的函数值； 如果带到最大迭代次数或满足：
K-means-聚类算法研究综述
K-means聚类算法研究综述 摘要:总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数，算法流程，并列举了一个实例，指出了数据子集的数目K，初始聚类中心选取，相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means 聚类的进一步研究方向。 关键词：K-means聚类算法；NP难优化问题；数据子集的数目K；初始聚类中心选取；相似性度量和距离矩阵 Review of K-means clustering algorithm Abstract: K-means clustering algorithm is reviewed. K-means clustering algorithm is a NP hard optimal problem and global optimal result cannot be reached. The goal，main steps and example of K-means clustering algorithm are introduced. K-means algorithm requires three user-specified parameters: number of clusters K，cluster initialization，and distance metric. Problems and improvement of K-means clustering algorithm are summarized then. Further study directions of K-means clustering algorithm are pointed at last. Key words: K-means clustering algorithm; NP hard optimal problem; number of clusters K; cluster initialization; distance metric K-means聚类算法是由Steinhaus1955年、Lloyed1957年、Ball & Hall1965年、McQueen1967年分别在各自的不同的科学研究领域独立的提出。K-means聚类算法被提出来后，在不同的学科领域被广泛研究和应用，并发展出大量不同的改进算法。虽然K-means聚类算法被提出已经超过50年了，但目前仍然是应用最广泛的划分聚类算法之一[1]。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。 文中总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数、算法流程，并列举了一个实例，指出了数据子集的数目K、初始聚类中心选取、相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means聚类的进一步研究方向。 1经典K-means聚类算法简介 1.1K-means聚类算法的目标函数 对于给定的一个包含n个d维数据点的数据集 12 {x,x,,x,,x} i n X=??????，其中d i x R ∈，以及要生成的数据子集的数目K，K-means聚类算法将数据对象组织为 K个划分{c,i1,2,} k C K ==???。每个划分代表一个类c k，每个类c k有一个类别中心iμ。选取欧氏距离作为相似性和 距离判断准则，计算该类内各点到聚类中心 i μ的距离平方和 2 (c) i i k i k x C J xμ ∈ =- ∑（1） 聚类目标是使各类总的距离平方和 1 (C)(c) K k k J J = =∑最小。 22 1111 (C)(c) i i K K K n k i k ki i k k k x C k i J J x d x μμ ==∈== ==-=- ∑∑∑∑∑ （2）其中， 1 i i ki i i x c d x c ∈ ? =? ? ? 若 若 ，显然，根据最小二乘 法和拉格朗日原理，聚类中心 k μ应该取为类别 k c类各数据点的平均值。 K-means聚类算法从一个初始的K类别划分开始，然
基于K―means聚类的客户细分案例分析
基于K―means聚类的客户细分案例分析 【摘要】当今流行的客户细分理论的视角主要关注在消费市场的细分上，现有的客户细分理论中根据客户购买的产品特征进行细分的分析和研究相对较少，因此本文的研究就是把某品牌鞋子的风格特征作为细分变量，基于某企业的销售数据来进行分析，选择K-means聚类分析方法结合企业的实际情况，划分出不同的客户群，企业可以根据不同客户群的需求和对企业的贡献制定不同的宣传营销策略，降低企业的销售成本，提高企业的竞争力。 【关键词】客户细分K-means聚类案例分析营销策略 一、案例介绍 某公司是一个以鞋类的研发制造及品牌管理为主的时 尚集团公司，业务遍及大中华区（中国大陆、香港、台湾）、亚洲、欧洲及北美洲，是中国最成功的国内品牌之一。该公司在中国经营的组织架构为：总公司――分公司――专卖店。其中，总公司负责拓展策略和公司年度工作计划的制定，以及成本控制和分公司事务管理。分公司负责执行总公司的战略，对专卖店、专卖店人员实施管理，工作内容包括：新开专卖店寻址、申请开店、签约、开店；对分公司人员管理、分公司销售指标达成、执行总公司促销活动等。
二、数据处理 （一）数据准备 原始数据包括两张表：客户交易记录表和鞋子具体属性表，其中客户交易记录表与鞋子属性表连接的变量是鞋子ID，交易记录数据的时间是过去一年2013年9月1日到2014年9月1日。 （二）数据清洗 该企业一年的交易记录有几千万条，所以原始的交易数据量非常大，这样就很容易出现噪声数据、空缺数据和不一致数据，所以必须要经过一系列的分析与处理，包括对缺失值的处理和异常值的处理，例如：去除客户属性为空的客户记录、剔除消费额和消费次数不在正常范围内的客户记录等。 （1）剔除异常的正负交易。从客户交易记录表中选出过去一年交易ID不为空的正常交易记录，交易记录表中的金额有正负之分，正表示购买记录，负表示退货记录，要剔除掉没有正交易与之对应的退货记录。 （2）剔除异常的购买数量和金额。由于有些客户不是会员，专卖店的销售员会帮客户刷自己的会员卡，这样就会出现一个会员ID在一段时间内交易数量和交易金额超出正常范围。本文用3δ准则剔除不在正常范围内异常客户。 （三）数据转换和整合
(完整版)X-means：一种针对聚类个数的K-means算法改进
X-means：一种针对聚类个数的K-means算法改进 摘要 尽管K-means很受欢迎，但是他有不可避免的三个缺点：1、它的计算规模是受限的。2、它的聚类个数K必须是由用户手动指定的。3、它的搜索是基于局部极小值的。在本文中，我们引入了前两种问题的解决办法，而针对最后一个问题，我们提出了一种局部补救的措施。根据先前有关算法改进的工作，我们引入了一种根据BIC（Bayesian Information Criterion）或者AIC（Akaike information criterion）得分机制而确定聚类个数的算法，本文的创新点包括：两种新的利用充分统计量的方式，还有一种有效地测试方法，这种方法在K-means算法中可以用来筛选最优的子集。通过这样的方式可以得到一种快速的、基于统计学的算法，这种算法可以实现输出聚类个数以及他们的参量值。实验表明，这种技术可以更科学的找出聚类个数K值，比利用不同的K值而重复使用K-means算法更快速。 1、介绍 K-means算法在处理量化数据中已经用了很长时间了，它的吸引力主要在于它很简单，并且算法是局部最小化收敛的。但是它有三点不可避免的缺点：首先，它在完成每次迭代的过程中要耗费大量的时间，并且它所能处理的数据量也是很少的。第二，聚类个数K值必须由用户自身来定义。第三，当限定了一个确定的K值时，K-means算法往往比一个动态K值的算法表现的更差。我们要提供针对这些问题的解决办法，通过嵌入树型的数据集以及将节点存储为充分统计变量的方式来大幅度提高算法的计算速度。确定中心的分析算法要考虑到泰森多边形边界的几何中心，并且在估计过程的任何地方都不能存在近似的方法。另外还有一种估计方法，“黑名单”，这个列表中将会包含那些需要在指定的区域内被考虑的图心。这种方法不仅在准确度上以及处理数据的规模上都表现的非常好，而这个快速算法在X-means 聚类算法当中充当了结构算法的作用，通过它可以很快的估计K值。这个算法在每次使用 K-means算法之后进行，来决定一个簇是否应该为了更好的适应这个数据集而被分开。决定的依据是BIC得分。在本文中，我们阐述了“黑名单”方法如何对现有的几何中心计算BIC 得分，并且这些几何中心所产生的子类花费不能比一个单纯的K-means聚类算法更高。更进一步的，我们还通过缓存状态信息以及估计是否需要重新计算的方法来改善估计方法。 我们已经用X-means算法进行了实验，验证了它的确比猜K值更加科学有效。X-means 算法可以在人造的或者是真实数据中表现的更好，通过BIC得分机制。它的运行速度也是比K-means更快的。 2、定义 我们首先描述简单的K-means算法应该考虑哪些因素。通过K-means可以把一定量的数据集分为K个数据子集，这K个数据子集分别围绕着K个聚类中心。这种算法保持着K个聚类中心不变，并且通过迭代不断调整这K个聚类中心。在第一次迭代开始之前，K个聚类中心都是随机选取的，算法当聚类中心不再变化的时候返回最佳的结果，在每一次迭代中，算法都要进行如下的动作： 1、对于每一个节点向量，找到距离它最近的聚类中心，归入此类。 2、重新评估每一个图心的位置，对于每一个图心，必须是簇的质心。 K-means聚类算法通过局部最小化每个向量到对应图心的距离来实现聚类。同时，它处理真实数据时是非常慢的。许多情况下，真实的数据不能直接用K-means进行聚类，而要经过二次抽样筛选之后再进行聚类。Ester曾经提出了一种可以从树形数据中获得平衡的抽样数据的方法。Ng和Han曾经提出了一种可以指导概率空间对输入向量的检索模拟模型。
K-means聚类算法基本思想讲解学习
K-m e a n s聚类算法基 本思想
精品文档 K-means聚类算法基本思想 聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。K-means也是聚类算法中最简单的一种。以星团划分为例，，首先随机选取k个宇宙中的点（或者k个星星）作为k 个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距离，然后选取距离最近的那个星团作为 ，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心（对里面所有的 星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。 K-means也是聚类算法中最简单的一种了，但是里面包含的思想却是不一般。最早我使用并实现这个算法是在学习韩爷爷那本数据挖掘的书中，那本书比较注重应用。看了Andrew Ng的这个讲义后才有些明白K-means后面包含的EM思想。 聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设宇宙中的星星可以表示成三维空间中的点集。 聚类的目的是找到每个样本x潜在的类别y，并将同类别y的样本x放在一起。比如上面的星星，聚类后结果是一个个星团，星团里面的点相互距离比较近，星团间的星星距离就比较远了。 在聚类问题中，给我们的训练样本是，每个，没有了y。 K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下： 1、随机选取k个聚类质心点（cluster centroids）为。 2、重复下面过程直到收敛 { 对于每一个样例i，计算其应该属于的类 对于每一个类j，重新计算该类的质心 } K是我们事先给定的聚类数，代表样例i与k个类中距离最近的那个类，的值是1到k中的一个。质心 代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距 离，然后选取距离最近的那个星团作为，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。 下图展示了对n个样本点进行K-means聚类的效果，这里k取2。 收集于网络，如有侵权请联系管理员删除
基于K-MEANS聚类的电商网站用户行为分析
第38卷第3期温州大学学报（自 然 科 学 版）2017年8月V ol 38, No 3 Journal of Wenzhou University (Natural Science Edition) Aug, 2017 基于K-MEANS聚类的电商网站用户行为分析 王召义，薛晨杰 (安徽商贸职业技术学院经济贸易系，安徽芜湖 241002) 摘要：调整网站访问日志数据，从中提取用户访问各类页面次数，考虑类别化的变量组合方式，采 用K-MEANS聚类对类别化的变量进行聚类分析，理解各类别特征，描述用户行为，分析各类别与输 出结果的关联性，并为制定网站经营策略提供支持和参考依据．实证研究表明，对页面访问次数占比 进行K-MEANS聚类分析，可以明确各类型页面与输出结果之间的关联性． 关键词：K-MEANS聚类；用户行为；多元回归；输出结果 中图分类号：TP311.13 文献标志码：A 文章编号：1674-3563(2017)03-0049-06 DOI：10.3875/j.issn.1674-3563.2017.03.008 本文的PDF文件可以从https://www.docsj.com/doc/6516350937.html,获得 用户行为主要是指用户在使用网络资源时所呈现出来的规律，可以用某些特征量的统计特征或特征量的关联关系定量或定性地表示[1]．购物网站的用户行为特征更有其独特之处，通过数据挖掘技术分析购物网站的用户行为特征，己成为电子商务用户流失领域的一个重要研究课题[2]．1 问题由来 现在的中小企业在互联网的冲击下，有的被时代淘汰，有的则搭乘互联网+的浪潮，摇身一变成了有着独立购物网站的电子商务企业[3]．独立购物网站在给企业带来机遇的同时，也面临着一系列的问题——网站如何推广、流量从哪里来、如何识别用户访问行为特征等，这些问题处理不好，会拖累企业发展．分析网站访问日志是解决这些问题的有效手段之一，通过分析网站访问日志能了解用户行为及被频繁访问的资源．因此，本文从大量网站访问日志数据中提取有关数据，使用K-MEANS聚类对这些数据进行分析，描述用户行为特征，从而为制定网站经营策略提供支持和参考依据． 2 研究模型 基于K-MEANS聚类的网站用户行为分析，其核心是对网站访问日志数据进行聚类分析，描述各类别的特征，并分析各类别与输出结果的关联性．研究模型主要分为三个部分：数据准备、数据分析和结论．具体流程如图1． 1）数据准备 从企业自建的购物网站访问日志中提取出用户访问各类页面的次数，并计算出各页面类型访 收稿日期：2016-09-30 基金项目：安徽省高校优秀青年人才支持计划项目(gxyqZD2017110)；安徽省高校人文社会科学研究重点项目(SK2016A0357)；安徽省教学研究项目(2015jyxm751)；安徽省高校自然科学研究重点项目(KJ2016A253) 作者简介：王召义(1983-)，男，安徽宿州人，讲师，硕士，研究方向：数据挖掘
K-Means聚类算法及实现代码
K-Means算法 k-means 算法接受参数k ；然后将事先输入的n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 假设要把样本集分为c个类别，算法描述如下： （1）适当选择c个类的初始中心； （2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类； （3）利用均值等方法更新该类的中心值； （4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。 #include
(完整版)matlab实现Kmeans聚类算法
题目：matlab实现Kmeans聚类算法 姓名 学号
背景知识 1.简介： Kmeans算法是一种经典的聚类算法，在模式识别中得到了广泛的应用，基于Kmeans的变种算法也有很多，模糊Kmeans、分层Kmeans 等。 Kmeans和应用于混合高斯模型的受限EM算法是一致的。高斯混合模型广泛用于数据挖掘、模式识别、机器学习、统计分析。Kmeans 的迭代步骤可以看成E步和M步，E：固定参数类别中心向量重新标记样本，M：固定标记样本调整类别中心向量。K均值只考虑（估计）了均值，而没有估计类别的方差，所以聚类的结构比较适合于特征协方差相等的类别。 Kmeans在某种程度也可以看成Meanshitf的特殊版本，Meanshift 是一种概率密度梯度估计方法（优点：无需求解出具体的概率密度，直接求解概率密度梯度。），所以Meanshift可以用于寻找数据的多个模态（类别），利用的是梯度上升法。在06年的一篇CVPR文章上，证明了Meanshift方法是牛顿拉夫逊算法的变种。Kmeans 和EM算法相似是指混合密度的形式已知（参数形式已知）情况下，利用迭代方法，在参数空间中搜索解。而Kmeans和Meanshift相似是指都是一种概率密度梯度估计的方法，不过是Kmean选用的是特殊的核函数（uniform kernel），而与混合概率密度形式是否已知无关，是一种梯度求解方式。 k-means是一种聚类算法，这种算法是依赖于点的邻域来决定哪些
点应该分在一个组中。当一堆点都靠的比较近，那这堆点应该是分到同一组。使用k-means，可以找到每一组的中心点。 当然，聚类算法并不局限于2维的点，也可以对高维的空间（3维，4维，等等）的点进行聚类，任意高维的空间都可以。 上图中的彩色部分是一些二维空间点。上图中已经把这些点分组了，并使用了不同的颜色对各组进行了标记。这就是聚类算法要做的事情。 这个算法的输入是： 1：点的数据（这里并不一定指的是坐标，其实可以说是向量） 2：K，聚类中心的个数（即要把这一堆数据分成几组） 所以，在处理之前，你先要决定将要把这一堆数据分成几组，即聚成几类。但并不是在所有情况下，你都事先就能知道需要把数据聚成几类的。但这也并不意味着使用k-means就不能处理这种情况，下文中会有讲解。 把相应的输入数据，传入k-means算法后，当k-means算法运行完后，该算法的输出是： 1：标签（每一个点都有一个标签，因为最终任何一个点，总会被分到某个类，类的id号就是标签） 2：每个类的中心点。 标签，是表示某个点是被分到哪个类了。例如，在上图中，实际上
基于K-Means聚类的数据分析
现代制造技术与装备 8 2017第4期 总第245期 1 K-Means 聚类算法概述1.1 内涵 K-Means 算法是对对象元素之间差异问题检测的聚类算法。它主要是从所有的样本对象中选择出K 个元素作为最开始的聚类目标，之后按照规则算法要求，对剩下元素和目标中心元素之间距离进行分析，根据计算的数值确定元素和中心元素之间的关系。K-Means 聚类算法流程操作，如图1 所示。 图1 K-Means 聚类算法图 1.2 局限 K-Means 聚类算法包括划分法、层次法和基于模型的算法。这些算法的缺点是对样本数据进行了假设处理，而这种假设处理方式无法在大数据收集和整理中发挥作用。同时，K-Means 聚类算法能够挖掘的聚类个数依赖用户指定的参数信息，使用上对用户要求过高。 2 基于MapReduce 分布式K-Means 聚类数据优化分析2.1 初始阶段聚类中心优化 传统K-Means 算法中心的选择具有很强的随意性，使得算法在获得局部最优值时会停止。K-Means 聚类算法研究的重点之一是获得算法的终止最优解。应用Canopy 聚类能够对中心初始数据进行优化，对于在各个集群中的数据子 集，可以应用Canopy 算法计算产生多个局部中心，之后应用局部中心获得全局中心数据的集合。2.2 迭代优化 K-Means 聚类的迭代优化过程需要计算数据对象到每一个簇中心的距离，并对簇中心所属类型进行标注。创建Canopy 聚类时，需要保证划分后的簇至少包含这个簇的一个元素，每一个数据点都需要落在Canopy 上。K-Means 聚类结果示意图，如图2所示，实现圈代表的是重叠之后的canopy。实际上，数据点分布在虚线圈的五个簇中。在这五个簇中，每一个至少包含一个canopy。簇A 例外，被两个canopy 包含。 根据canopy 的基础上，对分布在现有站点数据子集独享进行分析，通过Map 函数计算出Canopy 聚类和哪一个簇的中心距离近。具体方法：先判断数据对象和簇中心是否同属于一个canopy，之后通过降低聚类算法实现对全部数 据对象的精确计算。 图2 K-Means 聚类结果示意图 2.3 算法实现 实现K-means 聚类优化算法分四个阶段，应用四个Job 完成，具体流程如图3所示。其中，Job1需要产生K 个canopy 中心；Job2需要在Job1的基础上生产K 个能够互相重叠的canopy；Job3主要是对同一个canopy 数据对象进行K-means 聚类分析，之后形成簇；Job4是通过应用稳定下来的K-means 中心簇类，获得最终的输出结果。3 K-Means 聚类算法在学生成绩数据分析中的应用3.1 数据的预处理 应用教育统计中的标准分数，对学生的考试成绩进行分析。学生考试成绩的标准分数是一种相对数值，不受原 基于K-Means 聚类的数据分析 易雁飞 （广东工业大学 自动化学院，广州 511400） 摘 要：K-Means 是一种常见的划分聚类算法，是在集中式系统框架无法对海量数据进行处理分析的基础上提出的。基于K-Means 聚类数据分析算法，优化初始中心数据的选取，改革数据传输通信和计算模式。实验证明，这种算法具有很强的执行效率和扩展性，适合应用到大量的数据挖掘分析中。为此，文章对基于K-Means 聚类的数据进行分析。 关键词：K-Means 聚类 数据分析 算法 DOI:10.16107/https://www.docsj.com/doc/6516350937.html,ki.mmte.2017.0197