应用聚类(实验题)

1聚类方法---K均值算法（K-means）应用举例一．算法按照聚类的原理和方法，主要的聚类算法可以分为以下几类：(1)基于划分的聚类：包括1）k平均算法或称k均值算法（K-means）；2）k中心点算法。(2)基于层次的聚类;(3)基于密度的聚类;(4)基于网格的聚类;(5)基于模型的聚类.k均值（K-means）算法是一种简单使用的无监督学习算法，此种方法能够用于已知类数K的数据聚类和分析，基本步骤如下：初始化：给定类的个数k,置j=0,从样本向量中任意选定k个向量jkjjccc,...,,21作为聚类中心，],...,,[21jinjijijicccc，（ki,...,2,1）。其中，n为输入向量的维数，并记中心为jic的聚类块jiC。（1）将每个样本向量Tnllllxxxx],...,,[21，按下列欧几里得距离归入中心为jic的类中。jmlkmjilcxcx1min（1）（2）从新调整聚类中心，新的聚类中心1jic由下式计算得出，即iCxmljimNxcjiili1，式中：iN是聚类块jiC中的向量数。（3）如果（1）中的聚类中心jic（ki,...,2,1）不再明显2变换，就终止，否则1ji，转（1）。上述方法是一种迭代算法，可以采用下面的目标函数进行迭代，直到J不再明显改变为止。nkCxikikcxJ1二.算法应用在本例中，利用k均值聚类方法，分析大中城市城镇居民家庭情况的相似性，表1为35个大中城市城镇居民家庭基本情况表。把35个大中城市分为五类，每个城市用7个属性描述，即样本个数为35，样本向量维数7，采用K均值聚类算法进行分类，在算法公式（1）中，向量的维数n=7，聚类个数k=5，样本向量个数l35。本例采用SQLServer2005平台工具进行数据挖掘。3表14三.实验结果通过K均值算法把35个大中城市聚成五个类，每类的城市数量：分类1为13，分类2为9，分类3为8，分类4为3，分类5为2，下表所示。分类1分类2分类3分类4分类55附录：SQLServer2005数据挖掘平台——Microsoft聚类分析算法参数介绍：6CLUSTERCOUNT参数:指定将由算法生成的大致分类数，如果无法基于相应的数据生成该大致数目的分类，则算法将生成尽可能多的分类，在实际问题中，待分类数据的属性越多，则分类的数目也应该相应增多。CLUSTER_SEED参数:它指定在为建模初始阶段随机生成分类时所要使用的种子数字。默认值0。CLUSTERING_METHOD参数：指选用何种方法进行聚类划分，SQLServer2005Microsoft聚类挖掘提供了以下4种方法：1---ScalableEM(default):可缩放聚类分析框架下的EM方法（默认）；2---Vanilla(non-scalable)EM:普通的（非可缩放聚类分析框架）7EM方法；3---ScalableK-means:可缩放聚类分析框架下的K方法；4---Vanilla(non-scalable)K-means:普通的（非可缩放聚类分析框架）K方法。注：SQLServer2005Microsoft聚类分析提供的上面4种方法都是基于划分的方法，其中包括EM方法和K方法（K-means）。EM方法：又称为最大期望方法（expectationmaximization,简称EM）该方法没有直接采用计算距离的方法，而是采用概率方法来将每一个数据分配到待定分类中，该方法在每一个维度上设置一个封闭曲线作为聚类标准，并计算平均数与标准差。如果一个点落在这个封闭曲线内，则认为这个点有一定的几率属于这个给定分类。由于不同分类所对应曲线并不唯一，因此某个数据点可能同时落在多个分类曲线中，并被赋予相应概率。由于EM方法可以允许分类边界模糊而又有重叠，故被称为软聚类，这种方法比较适合不脱节的聚类。K方法（K-means）：通过测量数据与预先划分好的分类的“距离”来决定数据属于哪一个分类，这里所谓的“距离”采用最简单的欧几里得距离定义，每一个对象被划分到距离分类中心最近的分类中。这里K方法的K就是指划分分类的数目，因为K方法可以将每一个数据不重不漏地分配到每一个待定分类中，故被称为硬聚类。8何谓可缩放聚类分析框架：在进行聚类分析时，通常会遇到这样问题，为了得到较好的分类划分方式，需要不断的采用已有的数据对给定的划分方式进行测试，对于小的测试数据集，可以存储在内存中，存储都十分迅速，在时间上一切都没有问题，可随着测试数据的增长，数据已经无法完全存储在内存中，就无法对每个数据进行计算比较，且时间上也无法忍受，可以采用可缩放聚类分析框架，对数据集进行高效的聚类分析而不考虑数据量的大小，这样当进行重复训练时，将不会在不同分类之间来回移动地测试数据压缩，不把这些数据载入内存，从而腾出更多的空间存储数据。MAXIMUM_INPUT_ATTRIBUTES参数:用于设置聚类分析中，在进行自动特征识别前需要考虑每一个数据特征量的数目，如果数据集中拥有多于这个数目的数据特征，则特征识别会选择数据集中最常见的特征，而其他的数据特征将被忽略，因为特征量的数目会对分析效率产生较大的影响，故被设置为一个有限值，默认值为255。MAXIMUM_STATES参数:该参数用于设置每一个数据特征拥有集中状态，如果一个数据特征拥有的状态数超过这个数值，则系统会选择最常见的状态，其他的状态被设置为others,同样因为这个量会影响到分析效率与内存占用，故被设置为一个有限值，默认值100。MINIMUM_SUPPORT参数:如果某个分类聚类后得到的数据小于9Minimum_Support,则这个分类被认为是空的，被抛弃或重新初始化。通常可以不必改变这个参数，除非实际的模型中确实有这项限制，默认值0。MODELLING_CARDINALITY参数:在聚类过程中生成候选模型的数目，有这个参数控制，如果减少这个参数值可以提高聚类效率，但是存在有降低聚类精度的危险，默认值10。STOPPING_TOLERANCE参数:设置模型收敛的极限值，当分类概率中的整体变化小于STOPPING_TOLERANCE参数与模型大小之比时，即达到收敛。这个值无论是在内部的每一次聚类测试中，还是在外部的缩放步骤中，都要进行校核。增大这个数值，可以使聚类算法迅速收敛，但会使分类模糊，反之减小这个参数可以使分类更加清晰。如果数据量比较小或者数据之间特点鲜明，则可以设置这个值为1，默认值10。SAMPLE_SIZE参数:它代表在可缩放聚类分析框架中每次提供样本的事例数。在Vanilla版中，Sample_Size指的是整个数据集的数据总量。减少这个数值有可能使模型收敛过早，尤其是当选择了较大的STOPPING_TOLERANCE。这个参数在数据量很大时，可以谨慎的使用。如果将参数值设置为0，则会在单个传递中对整个数据集进行聚类分析操作，从而导致内存和性能问题。注意，由于可缩放聚类分析框架本身的性能，对于不同的参数设置，有可能导致分析结果有细微的差异，默认值50000。