数据挖掘培训(上).ppt

用调整后的中心点再次进行聚类，得到： 第二次迭代后的结果为： 中国C，日本A，韩国A，伊朗A，沙特A，伊拉克C，卡塔尔C，阿联酋C，乌兹别克斯坦B，泰国C，越南C，阿曼C，巴林B，朝鲜B，印尼C。 结果无变化，说明结果已收敛，于是给出最终聚类结果： 亚洲一流：日本，韩国，伊朗，沙特 亚洲二流：乌兹别克斯坦，巴林，朝鲜 亚洲三流：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼 看来数据告诉我们，说国足近几年处在亚洲三流水平真的是没有冤枉他们，至少从国际杯赛战绩是这样的。 其实上面的分析数据不仅告诉了我们聚类信息，还提供了一些其它有趣的信息，例如从中可以定量分析出各个球队之间的差距，例如，在亚洲一流队伍中，日本与沙特水平最接近，而伊朗则相距他们较远，这也和近几年伊朗没落的实际相符。 * DMKD Sides By MAO * k-means算法的性能分析 主要优点： 是解决聚类问题的一种经典算法，简单、快速。 对处理大数据集，该算法是相对可伸缩和高效率的。 当结果簇是密集的，它的效果较好。 主要缺点 在簇的平均值被定义的情况下才能使用，可能不适用于某些应用。 必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。 不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。 K均值算法的改进 改进措施： （1）样本数据预处理。计算样本对象两两之间的距离，筛掉与其它所有样本的距离和最大的m个对象。 （2）初始聚类中心的选择。如不采用簇中的平均值作为参考点，而选用簇中位置最靠近中心的对象。这样可以避免孤立点的影响。 * DMKD Sides By MAO * k-means的几种改进方法 k-mode 算法：实现对离散数据的快速聚类，保留了k-means算法的效率同时将k-means的应用范围扩大到离散数据。 k-prototype算法：可以对离散与数值属性两种混合的数据进行聚类，在k-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。 k-中心点算法k -means算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。 k-mode 算法 k-prototype算法 K-MEDOIDS K-MEANS有其缺点：产生类的大小相差不会很大，对于脏数据很敏感。 改进的算法：k—medoids 方法。这儿选取一个对象叫做mediod来代替上面的中心的作用，这样的一个medoid就标识了这个类。K-medoids和K-means不一样的地方在于中心点的选取，在K-means中，我们将中心点取为当前cluster中所有数据点的平均值，在 K-medoids算法中，我们将从当前cluster 中选取这样一个点——它到其他所有（当前cluster中的）点的距离之和最小——作为中心点。[1] 步骤： 1，任意选取K个对象作为medoids（O1,O2,…Oi…Ok）。 以下是循环的： 2，将余下的对象分到各个类中去（根据与medoid最相近的原则）； 3，对于每个类（Oi）中，顺序选取一个Or，计算用Or代替Oi后的消耗—E（Or）。选择E最小的那个Or来代替Oi。这样K个medoids就改变了，下面就再转到2。 4，这样循环直到K个medoids固定下来。 这种算法对于脏数据和异常数据不敏感，但计算量显然要比K均值要大，一般只适合小数据量。 K-MEDOIDS Clara-Clarans Clara 上面提到K-medoids算法不适合于大数据量的计算。Clara算法，这是一种基于采样的方法，它能够处理大量的数据。 Clara算法的思想就是用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用K-medoids算法得到最佳的medoids。Clara算法从实际数据中抽取多个采样，在每个采样上都用K-medoids算法得到相应的（O1, O2 … Oi … Ok），然后在这当中选取E最小的一个作为最终的结果。 Clarans Clara算法的效率取决于采样的大小，一般不太可能得到最佳的结果。 在Clara算法的基础上，又提出了Clarans的算法，与Clara算法不同的是：在Clara算法寻找最佳的medoids的过程中，采样都是不变的。而Clarans算法在每一次循环的过程中所采用的采样都是不一样的。 与上面所讲的寻找最佳medoids的过程不同的是，必须人为地来限定循环的次数。 层次聚类方法概述 层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为： 凝聚的层次聚类：一种