迭代运算的调整规则。K-means算法以欧式距离作为相似度测度，它是求对应某一初始聚类中心向量V最有分类，使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。
2、原理探究
k个初始类聚类中心点的选取对聚类结果具有较大的影响，因为在该算法第一步中是随机的选取任意k个对象作为初始聚类的中心，初始地代表一个簇。该算法在每次迭代中对数据集中剩余的每个对象，根据其与各个簇中心的距离将每个对象重新赋给最近的簇。当考察完所有数据对象后，一次迭代运算完成，新的聚类中心被计算出来。如果在一次迭代前后，J的值没有发生变化，说明算法已经收敛。
公式为：E???i?1kp?Cip?mi
2其中E为数据库中所有对象的均方差之和，p为代表对象的空间中的一个点，
mi为聚类Ci的均值(p和mi均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
K-means 方法：在具有n 个对象的数据集中，随机选择k 个对象，每个对象初始的代表一个簇的中心，根据所采用的距离度量(如欧几里得距离度量)计算剩余的每个对象与这k 个初始簇中心点的距离，将对象分配到与其具有最小距离的簇中，这样具有n 个对象的数据集被划分成k 个簇，然后重新计算每个簇的平均值。该过程不断的循环迭代，直到新计算的平均值与上一次的平均值相比没有变化。从该方法的过程可以看出，当结果簇间具有明显的区别时，k-means 方法具有很好的效果，但是当存在孤立点时，孤立点对k-means 方法会产生很大的影响，因为平均值对孤立点很敏感。另外，k-means 方法需要事先指定聚类的数目。 3、算法过程
k-means 算法就是用得最多的一种传统的聚簇方法, 其算法核心思想如下: (1) 为每个聚类确定一个初始的聚类中心;
(2)这样k 个聚类存在k 个聚类中心, 将样本集中的每一个样本按照最小距离原则分配到k 个聚类中的某一个;
(3) 用每个聚类中所有样本的均值作为新的聚类中心;
(4) 类中心有变化则重复2、3 步直到聚类中心不再变化为止,最后得到的k 个聚类中心就是聚类的结果。
一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 采用两阶段反复循环过程算法，结束的条件是不再有数据元素被重新分配。
k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 具体如下： 输入：k, data[n];
（1） 选择k个初始中心点，例如c[0]=data[0],?c[k-1]=data[k-1]； （2） 对于data[0]?.data[n]，分别与c[0]?c[k-1]比较，假定与c[i]差值最少，就标记为i；
（3） 对于所有标记为i点，重新计算c[i]={ 所有标记为i的data[j]之和}/标记为i的个数；
（4） 重复(2)(3)，直到所有c[i]值的变化小于给定阈值。 下面给出K-means算法流程图：
开始Flag=1;InitData();FlagFTUpdateCluster(); UpdateCenter();IsEqual(Center,CenterCopy)T Flag=0;FCopyCenter();Print();free();结束
4、存在的问题
（1）在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目 K，例如 ISODATA 算法。关于 K-means 算法中聚类数目K 值的确定在文献中，是根据方差分析理论，应用混合 F 统计量来确定最佳分类数，并应用了模糊划分熵来验证最佳分类数的正确性。
（2）在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。对于该问题的解决，许多算法采用遗传算法（GA），例如文献 中采用遗传算法（GA）进行初始化，以内部聚类准则作为评价指标。
（3）从 K-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的侯选集。而在文献中，使用的 K-means 算法是对样本数据进行聚类，无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。
（4）K-means算法在计算簇内平均值时,很容易为初始值所影响。为了改进这个缺点,可以有两种改进方法：
① Kaufmam和Rous-seeuw采用了K-medoids算法,即用簇中位置最中心的点(中心点)来取代K-means算法中采用的簇中数据对象的平均值 。K-medoids算法的缺点在于:不适合对海量的数据进行聚类分析。一次迭代中的第一个循环阶段以及计算准则函数,与K-means算法的时间复杂度相同,但是在第二个循环阶段,更新每个簇的中心点随策略不同,复杂度和聚类结果也会产生差异。
K-medoids轮换法是K-medoids算法的一种变种算法,不仅具有K-medoids算法的优点,而且它采用的中心点更新策略能使准则函数下降最快。虽然这种算法以牺牲时间复杂度来换取更好的搜索性能,不适合数据量大的情况,但是在具体
运用时可选用此算法对整个数据集的一小部分数据进行聚类,来获取初始聚类中心点集,以此来降低整个数据集的聚类结果对初始聚类中心的影响。
②针对k-means算法对初值的依赖性，基于最小生成树原理选取聚类中心进行聚类。根据寻找最优初值的思想提出了一种改进的k-means算法，将最小生成树的构造算法之一的卡斯克鲁尔算法以及贪心算法的思想引入到kmeans算法中。设n个数据对象(数据点)，其中每个数据对象为d维，现要对这n个数据对象进行聚类，聚类数为k，集合U保存选择出来的初始数据中心点。首先根据Kruskal算法的思想进行k个中心数据点的选取，即先选取所有数据点中距离最远的两个数据点，将这两个数据点并入集合U中，若k>2，则在剩余的n-2个点中继续选择距集合U中数据点距离之和最大的数据点，并将其并入集合U中，直到U中数据中心点的个数等于k为止。
这里根据贪心算法的思想，进行初始数据中心点的选择，并不保证所选取出的k个数据点之间的距离之和最大。以U中的k个数据点作为初始数据中心点，按照kmeans算法进行聚类。算法中数据点之间的距离度量采用欧几里德距离，目标函数通常采用平方误差准则函数。改进后的k-means算法流程图如下：
改进算法具有比较好的聚类效果，整体分布比较均匀。与经典k-means算法比较，改进的算法具有以下特点：1.无需事先指定聚类中心；2.采用Kruskal算法，改进的k-means算法对异常值不敏感；3.采用贪心策略，使得聚类效率大大的提高。 （二）EM聚类
在 EM 聚类分析中，此算法反复优化初始分类模型以适合数据，并确定数据点存在于某个分类中的概率。当概率模型适合于数据时，此算法终止这一过程。用于确定是否适合的函数是数据适合模型的对数可能性。如果在此过程中生成空分类，或者一个或多个分类的成员身份低于给定的阈值，则具有低填充率的分类会以新数据点重设种子，并且 EM 算法重新运行。
EM 聚类分析方法的结果是概率性的。这意味着每个数据点都属于所有分类，但数据点向分类的每次分配都有一个不同的概率。因为此方法允许分类重叠，所以所有分类中的项的总数可能超过定型集中的总项数。在挖掘模型结果中，指示支持的分数会相应地调整以说明这一情况。
EM 算法与 k-means 聚类分析算法相比，它有多个优点：最多需要一次数据库扫描；工作时不受内存 (RAM) 限制；能够使用只进游标；优于抽样方法。
下面以一个实例来研究EM的算法。实验数据为“某城市年龄范围为25到55岁的中青年人调查数据样本”。使用的平台为SQL Server 2005。调查的数据项包括年龄、性别等。如图：
属性含义为：
通过仿真实验，得出的结果如下：
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据挖掘中聚类的理论研究(2)在线全文阅读。
相关推荐：