商务智能理论与应用6-k-means算法课案.ppt

K-means算法 李广明 ;聚类与分类的不同在于：分类作为一种监督学习方法，要求必须事先明确知道各个类别的信息，并且断言所有待分类项都有一个类别与之对应。但是很多时候上述条件得不到满足，尤其是在处理海量数据的时候，如果通过预处理使得数据满足分类算法的要求，则代价非常大，这时候可以考虑使用聚类算法。聚类属于无监督学习，相比于分类，聚类不依赖预定义的类和类标号的训练实例。 聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。;*;;;;对象间的相似度和相异度是基于两个对象间的距离来计算的。 标量也就是无方向意义的数字，也叫标度变量。现在先考虑元素的所有特征属性都是标量的情况。例如，计算X={2,1,102}和Y={1,3,2}的相异度。一种很自然的想法是用两者的欧几里得距离来作为相异度，欧几里得距离的定义如下： 其??义就是两个元素在欧氏空间中的集合距离，因为其直观易懂且可解释性强，被广泛用于标识两个标量元素的相异度。将上面两个示例数据代入公式，可得两者的欧氏距离为： 除欧氏距离外，常用作度量标量相异度的还有曼哈顿距离和闵可夫斯基距离，两者定义如下： ?? 曼哈顿距离： ??? 闵可夫斯基距离： ;上面这样计算相异度的方式有一点问题，就是取值范围大的属性对距离的影响高于取值范围小的属性。例如上述例子中第三个属性的取值跨度远大于前两个，这样不利于真实反映真实的相异度，为了解决这个问题，一般要对属性值进行规格化。所谓规格化就是将各个属性值按比例映射到相同的取值区间，这样是为了平衡各个属性对距离的影响。通常将各个属性均映射到[0,1]区间，映射公式为： 其中max(ai)和min(ai)表示所有元素项中第i个属性的最大值和最小值。例如，将示例中的元素规格化到[0,1]区间后，就变成了X’={1,0,1}，Y’={0,1,0}，重新计算欧氏距离约为1.732。 ;;*;分类变量是二元变量的推广，类似于程序中的枚举变量，但各个值没有数字或序数意义，如颜色、民族等等，对于分类变量，用“取值不同的同位属性数/单个元素的全部属性数”来标识其相异度。 序数变量是具有序数意义的分类变量，通常可以按照一定顺序意义排列，如冠军、亚军和季军。对于序数变量，一般为每个值分配一个数，叫做这个值的秩，然后以秩代替原值当做标量属性计算相异度。 ;对于向量，由于它不仅有大小而且有方向，所以闵可夫斯基距离不是度量其相异度的好办法，一种流行的做法是用两个向量的余弦度量，其度量公式为： 其中||X||表示X的欧几里得范数。要注意，余弦度量度量的不是两者的相异度，而是相似度！ ;划分方法 层次方法 基于密度的方法 基于网格的方法 基于模型的方法 基于约束的方法;基本思想：给定n个对象或数据元组的数据库，划分方法构建数据的k个划分，每一个划分表示一个簇，k=n。划分方法创建一个初始划分，然后采用迭代重定位技术，尝试通过对象在组间的移动来改进划分。 典型的划分方法有（1）k均值算法，其中每个簇都用该簇中对象的均值来表示。（2）k中心点算法，其中每个簇用接近簇中心的一个对象来表示。 它们的异同点有：k-均值算法和k-中心算法都属于聚类分析中的划分方法；k-均值算法是将簇中对象的均值作为簇的中心，可以是一个虚点，计算其他点与各个簇中心距离，归入距离最近的簇中；k-中心算法是找簇中最中心的点作为簇中心，是一个实际存在数据点。这只是均值与中心区别，两种算法具体流程还是不同的。 ;k平均聚类发明于1956年， 该算法最常见的形式是采用被称为劳埃德算法(Lloyd algorithm)的迭代式改进探索法。劳埃德算法首先把输入点分成k个初始化分组，可以是随机的或者使用一些启发式数据。然后计算每组的中心点，根据中心点的位置把对象分到离它最近的中心，重新确定分组。继续重复不断地计算中心并重新分组，直到收敛，即对象不再改变分组（中心点位置不再改变）。 ;K均值算法是基于质心的技术，k均值算法以k为输入参数，把n个对象集合分为k个簇，使得簇内的相似度高，簇间的相似度低。簇的相似度是关于簇中对象的均值度量，可以看作簇的质心。 K均值算法的处理流程如下，首先，随机的选择k个对象，每个对象代表一个簇的初始均值，对剩余的每个对象，根据其与各个簇均值的距离。将它指派到最相似的簇。然后计算每个簇的新均值，这个过程不断的重复，直到准则函数收敛。通常采用平方误差准则 这里Jc（m）是数据库中所有对象的平方误差的总和，Xi是空间中的点，表示给定的数据对象，Zj是簇Cj的平均值（ Xi和Zj都是多维的）。 ;算法：k均值。用于划分的k均值算法，每个簇的中心用簇中对象的均值来表示。 输入：k:簇的数目， D:包