`
thd52java
  • 浏览: 71976 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Mahout系列之----kmeans 聚类

阅读更多

Kmeans是最经典的聚类算法之一,它的优美简单、快速高效被广泛使用。

Kmeans算法描述

输入:簇的数目k;包含n个对象的数据集D。

输出:k个簇的集合。

方法:

  1. 从D中任意选择k个对象作为初始簇中心;
  2. repeat;
  3. 根据簇中对象的均值,将每个对象指派到最相似的簇;
  4. 更新簇均值,即计算每个簇中对象的均值;
  5. 计算准则函数;
  6. until准则函数不在发生变化。

Kmeans 算法的优缺点:

1)优点
(1)k-平均算法是解决聚类问题的一种经典算法,算法简单、快速。
(2)对处理大数据集,该算法是相对可伸缩的和高效率的,因为它的复杂度大约是O(nkt),其中n是所有对象的数目,k是簇的数目,t是迭代的次数。通常k<<n。这个算法经常以局部最优结束。
(3)算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的,而簇与簇之间区别明显时,它的聚类效果很好。
2)缺点
(1)k-平均方法只有在簇的平均值被定义的情况下才能使用,不适用于某些应用,如涉及有分类属性的数据不适用。
(2)要求用户必须事先给出要生成的簇的数目k。
(3)对初值敏感,对于不同的初始值,可能会导致不同的聚类结果。
(4)不适合于发现非凸面形状的簇,或者大小差别很大的簇。
(5)对于"噪声"和孤立点数据敏感,少量的该类数据能够对平均值产生极大影响。

针对算法存在的问题,对K-means算法提出一些改进:一是数据预处理,二是初始聚类中心选择,三是迭代过程中聚类种子的选择。

        首先对样本数据进行正规化处理,这样就能防止某些大值属性的数据左右样本间的距离。给定一组含有n个数据的数据集,每个数据含有m个属性,分别计算每一个属性的均值、标准差对每条数据进行标准化。

       其次,初始聚类中心的选择对最后的聚类效果有很大的影响,原K-means算法是随机选取k个数据作为聚类中心,而聚类的结果要是同类间尽可能相似,不同 类间尽可能相异,所以初始聚类中心的选取要尽可能做到这一点。采用基于距离和的孤立点定义来进行孤立点的预先筛选,并利用两两数据之间的最大距离在剩余数 据集合中寻找初始聚类中心。但对于实际数据,孤立点个数往往不可预知。在选择初始聚类中心时,先将孤立点纳入统计范围,在样本中计算对象两两之间的距离, 选出距离最大的两个点作为两个不同类的聚类中心,接着从其余的样本对象中找出已经选出来的所有聚类中心的距离和最大的点为另一个聚类中心,直到选出k个聚 类中心。这样做就降低了样本输入顺序对初始聚类中心选择的影响。

       聚类中心选好以后,就要进行不断的迭代计算,在K-means算法中,是将聚类均值点(类中所有数据的几何中心点)作为新的聚类种子进行新一轮的聚类计 算,在这种情况下,新的聚类种子可能偏离真正的数据密集区,从而导致偏差,特别是在有孤立点存在的情况下,有很大的局限性。在选择初始中心点时,由于将孤 立点计算在内,所以在迭代过程中要避免孤立点的影响。这里根据聚类种子的计算时,采用簇中那些与第k-1轮聚类种子相似度较大的数据,计算他们的均值点作 为第k轮聚类的种子,相当于将孤立点排除在外,孤立点不参与聚类中心的计算,这样聚类中心就不会因为孤立点的原因而明显偏离数据集中的地方。在计算聚类中 心的时候,要运用一定的算法将孤立点排除在计算均值点那些数据之外,这里主要采用类中与聚类种子相似度大于某一阈值的数据组成每个类的一个子集,计算子集 中的均值点作为下一轮聚类的聚类种子。为了能让更多的数据参与到聚类中心的计算种去,阈值范围要包含大多数的数据。在第k-1轮聚类获得的类,计算该类中 所有数据与该类聚类中心的平均距离S,选择类中与聚类种子相似度大于2S的数据组成每个类的一个子集,以此子集的均值点作为第k轮聚类的聚类种子。在数据 集中无论是否有明显的孤立点存在,两倍的平均距离都能包含大多数的数据。

 

对孤立点的改进:

      经典k均值算法中没有考虑孤立点。所谓孤立点都是基于距离的, 是数据U集中到U中最近邻居的距离最大的对象, 换言之, 数据集中与其最近邻居的平均距离最大的对象。针对经典k均值算法易受孤立点的影响这一问题, 基于距离法移除孤立点, 具体过程如下:

      首先扫描一次数据集, 计算每一个数据对象与其临近对象的距离, 累加求其距离和, 并计算出距离和均值。如果某个数据对象的距离和大于距离和均值, 则视该点为孤立点。把这个对象从数据集中移除到孤立点集合中, 重复直到所有孤立点都找到。最后得到新的数据集就是聚类的初始集合。

对初始点的选择和K值选择的改进:

     经典的kmeans 初值选择K值是很难确定的。由于kmeans是局部最优,所以对于初始中心选择很敏感,一方面影响聚类的速度,另一方面影响聚类的质量。一种思路是和其他 的聚类算法联合使用,比如Canopy ,谱聚类等。将Canopy和谱聚类执行的结果作为kmeans聚类的输入,这样效果就有了明显的提升。

Mahout Kmeans 聚类:

 

// 基于内存的 K 均值聚类算法实现
 public static void kMeansClusterInMemoryKMeans(){ 
 // 指定需要聚类的个数,这里选择 2 类
 int k = 2; 
 // 指定 K 均值聚类算法的最大迭代次数
 int maxIter = 3; 
 // 指定 K 均值聚类算法的最大距离阈值
 double distanceThreshold = 0.01; 
 // 声明一个计算距离的方法,这里选择了欧几里德距离
 DistanceMeasure measure = new EuclideanDistanceMeasure(); 
 // 这里构建向量集,使用的是清单 1 里的二维点集
 List<Vector> pointVectors = SimpleDataSet.getPointVectors(SimpleDataSet.points); 
 // 从点集向量中随机的选择 k 个作为簇的中心
 List<Vector> randomPoints = RandomSeedGenerator.chooseRandomPoints(pointVectors, k); 
 // 基于前面选中的中心构建簇
 List<Cluster> clusters = new ArrayList<Cluster>(); 
 int clusterId = 0; 
 for(Vector v : randomPoints){ 
	 clusters.add(new Cluster(v, clusterId ++, measure)); 
 } 
 // 调用 KMeansClusterer.clusterPoints 方法执行 K 均值聚类
 List<List<Cluster>> finalClusters = KMeansClusterer.clusterPoints(pointVectors, 
 clusters, measure, maxIter, distanceThreshold); 

 // 打印最终的聚类结果
 for(Cluster cluster : finalClusters.get(finalClusters.size() -1)){ 
	 System.out.println("Cluster id: " + cluster.getId() + 
" center: " + cluster.getCenter().asFormatString()); 
	 System.out.println("       Points: " + cluster.getNumPoints()); 	
 } 
 } 
 // 基于 Hadoop 的 K 均值聚类算法实现
 public static void kMeansClusterUsingMapReduce () throws Exception{ 
 // 声明一个计算距离的方法,这里选择了欧几里德距离
	 DistanceMeasure measure = new EuclideanDistanceMeasure(); 
	 // 指定输入路径,如前面介绍的一样,基于 Hadoop 的实现就是通过指定输入输出的文件路径来指定数据源的。
	 Path testpoints = new Path("testpoints"); 
	 Path output = new Path("output"); 
	 // 清空输入输出路径下的数据
 HadoopUtil.overwriteOutput(testpoints); 
	 HadoopUtil.overwriteOutput(output); 
	 RandomUtils.useTestSeed(); 
 // 在输入路径下生成点集,与内存的方法不同,这里需要把所有的向量写进文件,下面给出具体的例子
	 SimpleDataSet.writePointsToFile(testpoints); 
 // 指定需要聚类的个数,这里选择 2 类
 int k = 2; 
 // 指定 K 均值聚类算法的最大迭代次数
 int maxIter = 3; 
	 // 指定 K 均值聚类算法的最大距离阈值
 double distanceThreshold = 0.01; 
 // 随机的选择 k 个作为簇的中心
 Path clusters = RandomSeedGenerator.buildRandom(testpoints, 
 new Path(output, "clusters-0"), k, measure); 
 // 调用 KMeansDriver.runJob 方法执行 K 均值聚类算法
 KMeansDriver.runJob(testpoints, clusters, output, measure, 
 distanceThreshold, maxIter, 1, true, true); 
 // 调用 ClusterDumper 的 printClusters 方法将聚类结果打印出来。
 ClusterDumper clusterDumper = new ClusterDumper(new Path(output, 
"clusters-" + maxIter -1), new Path(output, "clusteredPoints")); 
 clusterDumper.printClusters(null); 
 } 
 //SimpleDataSet 的 writePointsToFile 方法,将测试点集写入文件里
 // 首先我们将测试点集包装成 VectorWritable 形式,从而将它们写入文件
 public static List<VectorWritable> getPoints(double[][] raw) { 
	 List<VectorWritable> points = new ArrayList<VectorWritable>(); 
 for (int i = 0; i < raw.length; i++) { 
		 double[] fr = raw[i]; 
		 Vector vec = new RandomAccessSparseVector(fr.length); 
		 vec.assign(fr); 
 // 只是在加入点集前,在 RandomAccessSparseVector 外加了一层 VectorWritable 的包装
		 points.add(new VectorWritable(vec)); 
	 } 
 return points; 
 } 
 // 将 VectorWritable 的点集写入文件,这里涉及一些基本的 Hadoop 编程元素,详细的请参阅参考资源里相关的内容
 public static void writePointsToFile(Path output) throws IOException { 
	 // 调用前面的方法生成点集
	 List<VectorWritable> pointVectors = getPoints(points); 
	 // 设置 Hadoop 的基本配置
	 Configuration conf = new Configuration(); 
	 // 生成 Hadoop 文件系统对象 FileSystem 
	 FileSystem fs = FileSystem.get(output.toUri(), conf); 
 // 生成一个 SequenceFile.Writer,它负责将 Vector 写入文件中
	 SequenceFile.Writer writer = new SequenceFile.Writer(fs, conf, output, 
	 Text.class,  VectorWritable.class); 
	 // 这里将向量按照文本形式写入文件
	 try { 
 for (VectorWritable vw : pointVectors) { 
 writer.append(new Text(), vw); 
		 } 
	 } finally { 
		 writer.close(); 
	 }  
 } 
1
2
分享到:
评论
2 楼 thd52java 2014-01-14  
0.5的。
1 楼 yeelor 2014-01-03  
这是用的mahout的哪个版本呢

相关推荐

    mahout聚类算法

    Mahout 聚类算法可以分为多种类型,如 Canopy、KMeans、Fuzzy-KMeans、Spectral Clustering 等,每种算法都有其自己的特点和应用场景。 在 Mahout 聚类算法中,数据模型是数据的基本结构,它可以是 DenseVector、...

    java 利用Kmeans的jar包进行聚类---代码

    这个标题"java 利用Kmeans的jar包进行聚类---代码"表明我们将探讨如何使用Java通过预编译的KMeans库(通常是一个jar包)来执行聚类任务。描述中的"java可以直接调用kmeans进行聚类!"进一步确认了Java程序员可以借助...

    mahout所需jar包

    Mahout的目标是帮助开发人员构建智能应用程序,如推荐系统、分类和聚类算法,这些在大数据分析领域中极为重要。 **K-Means聚类算法** K-Means是一种无监督学习的聚类算法,用于将数据集分成不同的群组或类别。在...

    mahout-distribution-0.5-src.tar.gz )

    1. **聚类算法**:KMeans是Mahout中最常见的聚类算法之一。在Hadoop上运行KMeans,可以处理海量数据,对大量用户行为、网站访问记录或者地理定位数据进行分组,发现潜在的模式或群体。此外,Mahout还支持其他聚类...

    maven_mahout_template-mahout-0.6

    kmeans聚类算法 基于划分的方法单机版基于学习

    mahout canopy+kmeans测试数据

    在Mahout中,测试数据往往是由一系列数值构成,这些数值代表了不同特征或维度上的测量值。例如,在上述部分数据中,可以看到一连串的数字,这可能代表了多维空间中的点坐标,或者是某个具体应用场景下的各种属性值。...

    mahout-demo:mahout 演示展示了它是如何工作的

    Mahout 演示欢迎来到驯象师演示。... 模糊 KMeans 聚类-. 冠层聚类(文档聚类) -. K均值聚类-. 模糊 KMeans 聚类使用 Maven 构建mvn 全新安装执行java -jar mahout-demo-0.0.1-SNAPSHOT-jar-with-dependencies.jar

    kmeans聚类java实现附测试数据及结果

    在Java中实现KMeans聚类,可以使用多种库,如Weka、Apache Mahout或自行编写代码。下面我们将深入探讨KMeans聚类的基本原理、Java实现的关键步骤以及如何进行测试和分析结果。 KMeans算法的核心思想是通过迭代过程...

    Kmeans文本聚类java实现

    在文件"**textcluster**"中,可能包含了实现这些功能的Java代码,如文本预处理类、KMeans聚类类、数据读取和输出功能等。具体实现细节,例如如何处理稀疏矩阵、如何优化距离计算等,可以通过阅读源代码来了解。 总...

    mahout0.9测试详细傻瓜说明

    以上步骤详细介绍了如何在 Mahout 0.9 中运行 KMeans 算法进行数据聚类。请注意,实际操作时可能需要根据你的具体环境配置和数据集调整相关参数,例如 KMeans 中的迭代次数、初始中心点选择策略等。此外,理解 ...

    coh-kmeans:用Java实现的半监督分层聚类算法

    K-means是最为知名的无监督聚类算法之一,而Coh-kmeans则是其半监督版本,结合了有监督和无监督的学习特性。本篇将深入探讨Coh-kmeans算法以及其Java实现。 ### 1. K-means算法简述 K-means算法基于中心点迭代更新...

    kmeans算法文本聚类java源码(分词,TF/IDF等)

    在Java环境中,我们可以使用开源库如Apache Mahout或自己编写代码实现KMeans算法。首先,构建TF-IDF矩阵,然后用Java编程实现KMeans算法的迭代过程。注意优化内存管理和并行计算以提高效率。 8. 整个工程运行 提供...

    mahout学习

    《深入理解Mahout中的KMeans聚类算法》 在数据挖掘和机器学习领域,聚类是一种常用的技术,用于发现数据集中的自然群体或类别。Apache Mahout作为一个强大的开源机器学习库,提供了多种聚类算法,其中KMeans是最为...

    synthetic_control.data

    Mahout的kmeans聚类测试数据

    mapreduce-kmeans:使用MapReduce的朴素K均值聚类

    mapreduce-kmeans 代码。 请注意,这只是一个示例,而不是可用于生产的代码。 如果您要进行正式生产和正常工作的群集,请使用Mahout,Hama或Spark。 建造 您将需要Java 8来构建该库。 您可以简单地使用以下命令...

    大数据技术 Hadoop开发者第二期 MapReduce HDFS Hive Mahout HBase 共64页.pdf

    - Kmeans 在推荐系统、聚类分析等领域的应用实例。 综上所述,这份资料涵盖了 Hadoop 相关技术的多个方面,包括分布式搜索引擎构建、数据处理、数据存储以及机器学习算法等。对于希望深入了解 Hadoop 生态系统的...

    mahout 0.4版本

    总结来说,Apache Mahout 0.4版本是一个强大的工具,为开发者和数据分析师提供了实现机器学习任务的高效途径,特别是KMeans聚类、FPM挖掘和协同过滤。通过这个开源项目,即使是对机器学习不熟悉的用户也能处理大数据...

    聚类分析 (4).pdf

    Apache Mahout是一个开源机器学习库,它提供了包括聚类分析在内的多种算法实现,支持Hadoop,使得大规模数据的聚类处理变得可能。通过Mahout,开发者可以轻松地实现各种聚类任务,探索和理解大数据集中的隐藏模式。 ...

    基于Spark框架的聚类算法研究

    大数据的挖掘是当今的研究热点,也有着巨大的商业价值。新型框架Spark部署在...该文研究了Spark中的机器学习中的聚类算法KMeans,先分析了算法思想,再通过实验分析其应用的方法,然后通过实验结果分析其应用场景和不足。

Global site tag (gtag.js) - Google Analytics