北京做网站公司排名浩森宇特,企业建设项目备案办法,微商怎么做,免费咨询法律问题的网站本文主要基于Anand Rajaraman和Jeffrey David Ullman合著#xff0c;王斌翻译的《大数据-互联网大规模数据挖掘与分布式处理》一书。KMeans算法是最常用的聚类算法#xff0c;主要思想是:在给定K值和K个初始类簇中心点的情况下#xff0c;把每个点(亦即数据记录)分到离其最近…本文主要基于Anand Rajaraman和Jeffrey David Ullman合著王斌翻译的《大数据-互联网大规模数据挖掘与分布式处理》一书。KMeans算法是最常用的聚类算法主要思想是:在给定K值和K个初始类簇中心点的情况下把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中所有点分配完毕之后根据一个类簇内的所有点重新计算该类簇的中心点(取平均值)然后再迭代的进行分配点和更新类簇中心点的步骤直至类簇中心点的变化很小或者达到指定的迭代次数。KMeans算法本身思想比较简单但是合理的确定K值和K个初始类簇中心点对于聚类效果的好坏有很大的影响。1. 确定K个初始类簇中心点最简单的确定初始类簇中心点的方法是随机选择K个点作为初始的类簇中心点但是该方法在有些情况下的效果较差如下(下图中的数据是用五个二元正态高斯分布生成的颜色代表聚类效果)《大数据》一书中提到K个初始类簇点的选取还有两种方法1)选择彼此距离尽可能远的K个点 2)先对数据用层次聚类算法或者Canopy算法进行聚类得到K个簇之后从每个类簇中选择一个点该点可以是该类簇的中心点或者是距离类簇中心点最近的那个点。1) 选择批次距离尽可能远的K个点首先随机选择一个点作为第一个初始类簇中心点然后选择距离该点最远的那个点作为第二个初始类簇中心点然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点以此类推直至选出K个初始类簇中心点。该方法经过我测试效果很好用该方法确定初始类簇点之后运行KMeans得到的结果全部都能完美区分五个类簇2) 选用层次聚类或者Canopy算法进行初始聚类然后利用这些类簇的中心点作为KMeans算法初始类簇中心点。常用的层次聚类算法有BIRCH和ROCK在此不作介绍下面简单介绍一下Canopy算法主要摘自Mahout的Wiki首先定义两个距离T1和T2T1T2.从初始的点的集合S中随机移除一个点P然后对于还在S中的每个点I计算该点I与点P的距离如果距离小于T1则将点I加入到点P所代表的Canopy中如果距离小于T2则将点I从集合S中移除并将点I加入到点P所代表的Canopy中。迭代完一次之后重新从集合S中随机选择一个点作为新的点P然后重复执行以上步骤。Canopy算法执行完毕后会得到很多Canopy可以认为每个Canopy都是一个Cluster与KMeans等硬划分算法不同Canopy的聚类结果中每个点有可能属于多个Canopy。我们可以选择距离每个Canopy的中心点最近的那个数据点或者直接选择每个Canopy的中心点作为KMeans的初始K个类簇中心点。2. K值的确定。《大数据》中提到给定一个合适的类簇指标比如平均半径或直径只要我们假设的类簇的数目等于或者高于真实的类簇的数目时该指标上升会很缓慢而一旦试图得到少于真实数目的类簇时该指标会急剧上升。类簇的直径是指类簇内任意两点之间的最大距离。类簇的半径是指类簇内所有点到类簇中心距离的最大值。废话少说上图。下图是当K的取值从2到9时聚类效果和类簇指标的效果图左图是K取值从2到7时的聚类效果右图是K取值从2到9时的类簇指标的变化曲线此处我选择类簇指标是K个类簇的平均质心距离的加权平均值。从上图中可以明显看到当K取值5时类簇指标的下降趋势最快所以K的正确取值应该是5.为以下是具体数据1 2个聚类2 所有类簇的半径的加权平均值 8.519166764433 所有类簇的平均质心距离的加权平均值 4.827162603224 3个聚类5 所有类簇的半径的加权平均值 7.584448294726 所有类簇的平均质心距离的加权平均值 3.376618248457 4个聚类8 所有类簇的半径的加权平均值 5.654896600649 所有类簇的平均质心距离的加权平均值 2.2213536045310 5个聚类11 所有类簇的半径的加权平均值 3.6747879855312 所有类簇的平均质心距离的加权平均值 1.2565764119513 6个聚类14 所有类簇的半径的加权平均值 3.4468699639815 所有类簇的平均质心距离的加权平均值 1.2094426414516 7个聚类17 所有类簇的半径的加权平均值 3.303664113518 所有类簇的平均质心距离的加权平均值 1.1665391918619 8个聚类20 所有类簇的半径的加权平均值 3.3026853030821 所有类簇的平均质心距离的加权平均值 1.1136163990622 9个聚类23 所有类簇的半径的加权平均值 3.1792440058224 所有类簇的平均质心距离的加权平均值 1.07431888569参考文献[1] 《大数据-互联网大规模数据挖掘与分布式处理》 Anand RajaramanJeffrey David Ullman著王斌译。
