聚类分析
聚类(Clustering)可以简单的理解为将数据对象分为多个簇(Cluster),每个簇 里的所有数据对象具有一定的相似性,这样一个簇可以看多一个整体对待,以此可以提高计算质量或减少计算量。而数据对象间相似性的衡量通常是通过坐标系中空间距离的大小来判断;常见的有 欧几里得距离算法、余弦距离算法、皮尔逊相关系数算法等,Mahout对此都提供了实现,并且你可以在实现自己的聚类时,通过接口切换不同的距离算法。
数据模型
在Mahout的聚类分析的计算过程中,数据对象会转化成向量(Vector)参与运算,在Mahout中的接口是org.apache.mahout.math.Vector 它里面每个域用一个浮点数(double)表示,你可以通过继承Mahout里的基类如:AbstractVector来实现自己的向量模型,也可以直接使用一些它提供的已有实现如下:
1. DenseVector,它的实现就是一个浮点数数组,对向量里所有域都进行存储,适合用于存储密集向量。
2. RandomAccessSparseVector 基于浮点数的 HashMap 实现的,key 是整形 (int) 类型,value 是浮点数(double) 类型,它只存储向量中不为空的值,并提供随机访问。
3. SequentialAccessVector 实现为整形 (int) 类型和浮点数 (double) 类型的并行数组,它也只存储向量中不 为空的值,但只提供顺序访问。
聚类算法K-means与Canopy
首先介绍先K-means算法:所有做聚类分析的数据对象,会被描述成n为空间中的一个点,用向量(Vector)表示;算法开始会随机选择K个点,作为一个簇的中心,然后其余的点会根据它与每个簇心的距离,被分配到最近簇中去;接着以迭代的方式,先重新计算每个簇的中心(通过其包含的所有向量的平均值),计算完成后对所有点属于哪个簇进行重新划分;一直如此迭代直到过程收敛;可证明迭代次数是有限的。
虽然K-means简单且高效,但它存在一定问题,首先K值(即簇的数量)是人为确定的,在对数据不了解的情况下,很难给出合理的K值;其次初始簇心的选择是随机的,若选择到了较孤立的点,会对聚类的效果产生非常大的影响。因此通常会用Canopy算法配合,进行初始化,确定簇数以及初始簇心。
Canopy算法首先会要求输入两个阀值 T1和T2,T1>T2;算法有一个集群这里叫Canopy的集合(Set),当然一开始它是空的;然后会将读取到的第一个点作为集合中的一个Canopy,接着读取下一个点,若该点与集合中的每个Canopy计算距离,若这个距离小于T1,则这个点会分配给这个Canopy(一个点可以分配给多个Canopy),而当这个距离小于T2时这个点不能作为一个新的Canopy而放到集合中。也就是说当一个点只要与集合中任意一个Canopy的距离小于T2了,即表示它里那个Canopy太近不能作为新的Canopy。若都没有则生成一个新的Canopy放入集合中。以此循环,直到没有点了。
所以这里用到的聚类分析算法的思路是:首先通过Canopy算法进行聚类,以确定簇数以及初始簇心的,接着通过K-means算法进行迭代运算,收敛出最后的聚类结果。接下来我们看看实现。
代码示例
在 mahout-examples 中的 org.apache.mahout.clustering.syntheticcontrol.kmeans.Job类,对上述算法提供了较完整的实现,它是一个Hadoop的job,我们从源代码入手,看如何将实际的数据跑起来。下面是该类的核心逻辑代码:
/**
* Run the kmeans clustering job on an input dataset using the given
* distance measure, t1, t2 and iteration parameters. All output data will
* be written to the output directory, which will be initially deleted if it
* exists. The clustered points will reside in the path
* <output>/clustered-points. By default, the job expects the a file
* containing synthetic_control.data as obtained from
* http://archive.ics.uci.
* edu/ml/datasets/Synthetic+Control+Chart+Time+Series resides in a
* directory named "testdata", and writes output to a directory named
* "output".
*
* @param conf
* the Configuration to use
* @param input
* the String denoting the input directory path
* @param output
* the String denoting the output directory path
* @param measure
* the DistanceMeasure to use
* @param t1
* the canopy T1 threshold
* @param t2
* the canopy T2 threshold
* @param convergenceDelta
* the double convergence criteria for iterations
* @param maxIterations
* the int maximum number of iterations
*/
public static void run(Configuration conf, Path input, Path output,
DistanceMeasure measure, double t1, double t2,
double convergenceDelta, int maxIterations) throws Exception {
System.out.println("run canopy output: " + output);
Path directoryContainingConvertedInput = new Path(output,
DIRECTORY_CONTAINING_CONVERTED_INPUT);
log.info("Preparing Input");
InputDriver.runJob(input, directoryContainingConvertedInput,
"org.apache.mahout.math.RandomAccessSparseVector");
log.info("Running Canopy to get initial clusters");
CanopyDriver.run(conf, directoryContainingConvertedInput, output,
measure, t1, t2, false, false);
log.info("Running KMeans");
System.out.println("kmeans cluster starting...");
KMeansDriver.run(conf, directoryContainingConvertedInput, new Path(
output, Cluster.INITIAL_CLUSTERS_DIR+"-final"), output, measure,
convergenceDelta, maxIterations, true, false);
// run ClusterDumper
ClusterDumper clusterDumper = new ClusterDumper(finalClusterPath(conf,
output, maxIterations), new Path(output, "clusteredPoints"));
clusterDumper.printClusters(null);
}
这个Job中调用了3个Map/Reduce 任务以及一个转换,它们如下:
1. 第8行: InputDriver.runJob ( ) ,它用于将原始数据文件转换成 Mahout进行计算所需格式的文件 SequenceFile,它是Hadoop API提供的一种二进制文件支持。这种二进制文件直接将<key, value>对序列化到文件中。
2. 第11行:CanopyDriver.run( ) , 即用Canopy算法确定初始簇的个数和簇的中心。
3. 第14行:KMeansDriver.run( ) , 这显然是K-means算法进行聚类。
4. 第18~20行,ClusterDumper类将聚类的结果装换并写出来,若你了解了源代码,你也可以自己实现这个类的功能,因为聚类后的数据存储格式,往往跟自身业务有关。
这里细讲下第一个Map/Reduce: InputDriver.runJob ( )因为我们需要了解,初始数据的格式,其他的任务CanopyDriver.run( )和KMeansDriver.run( )任务就不细讲了,主要就是Canopy和K-means算法,原理已经介绍了,实现也不难,需要你了解hadoop编程。
InputDriver.runJob( )实现也非常简单,它只有Map,其代码如下:
@Override
protected void map(LongWritable key, Text values, Context context) throws IOException, InterruptedException {
String[] numbers = SPACE.split(values.toString());
// sometimes there are multiple separator spaces
Collection<Double> doubles = Lists.newArrayList();
for (String value : numbers) {
if (!value.isEmpty()) {
doubles.add(Double.valueOf(value));
}
}
// ignore empty lines in data file
if (!doubles.isEmpty()) {
try {
Vector result = (Vector) constructor.newInstance(doubles.size());
int index = 0;
for (Double d : doubles) {
result.set(index++, d);
}
VectorWritable vectorWritable = new VectorWritable(result);
context.write(new Text(String.valueOf(index)), vectorWritable);
} catch (InstantiationException e) {
throw new IllegalStateException(e);
} catch (IllegalAccessException e) {
throw new IllegalStateException(e);
} catch (InvocationTargetException e) {
throw new IllegalStateException(e);
}
}
}
由代码可以看出,它将你初始数据文件的每一行用空格切开成个 String[] numbers ,然后再将 numbers中的每个String转换成Double类型,并以此生成一个向量 Vector ,然后通过 SequenceFileOutputFormat的方式输出成SequenceFile,以作下一步计算的输入。由此我们可以了解到我们的初始数据的格式需要 以一行为一个单位,用空格分隔,每一列为一个Double数即可(当然你也可以反过来修改例子中的实现)。
参考资料:
https://cwiki.apache.org/confluence/display/MAHOUT/K-Means+Clustering
https://cwiki.apache.org/confluence/display/MAHOUT/Canopy+Clustering
http://www.ibm.com/developerworks/cn/java/j-mahout-scaling/
http://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy3/
《Mahout in action》
https://cwiki.apache.org/MAHOUT/cluster-dumper.html
原创博客,转载请注明:http://my.oschina.net/BreathL/blog/58104
分享到:
相关推荐
Mahout的核心是它的聚类、分类、推荐系统和频繁项挖掘等算法,其中Canopy和K-means是其在聚类分析中的两个重要组成部分。 ### Mahout Canopy Canopy聚类算法是一种预聚类技术,常被用作K-means或其它更复杂的聚类...
2. **聚类(Clustering)**:包括K-means、Fuzzy K-means、Canopy Clustering等算法,用于将数据集中的对象分组到相似的类别中。这些算法广泛应用于市场细分、文本分类和图像分析等领域。 3. **分类...
2. 聚类(Clustering):包括K-Means、Fuzzy K-Means、Canopy Clustering等算法,用于将数据点自动分组到相似的集合中。 3. 分类(Classification):支持基于概率的朴素贝叶斯分类器(NaiveBayesTrainer)和其他...
3. **聚类**:包括K-means、Fuzzy K-means、Canopy Clustering等,用于将数据集分成多个具有相似特征的组。这些算法广泛应用于市场细分、用户分群和数据降维。 4. **矩阵分解**:如SVD(奇异值分解)和PMI(潜在...
Canopy 算法是为了解决层次聚类(如 K-Means)在处理大规模数据时计算效率低下的问题而设计的。它通过设定两个较大的半径 T1 和 T2 来快速过滤数据点,将相似的数据点进行预聚类,从而减少后续精确聚类算法的数据量...
3. **聚类**:包括K-Means、Fuzzy K-Means、Canopy Clustering、DBSCAN等算法,可用于将相似的数据点分组到一起,常用于市场细分、用户分群等场景。 4. **频繁项集挖掘**:通过Apriori、FP-Growth等算法发现数据...
- **聚类分析**:包括 K-Means、Canopy 等多种聚类算法。 - **分类**:如朴素贝叶斯分类器等。 这些功能帮助开发者处理大规模数据集,实现高效的数据挖掘和机器学习应用。 #### 3. Mahout 是怎么工作的? Mahout ...
3. **聚类**:K-Means、Fuzzy K-Means和Canopy Clustering等方法用于将数据分组到相似的集合中,无监督学习的一种常见应用。 4. **特征选择与降维**:通过PCA(主成分分析)和其他方法减少数据的维度,以便更有效地...
Mahout 0.5中的聚类算法包括K-Means、Fuzzy K-Means、Canopy Clustering等。这些算法用于发现数据集中的自然群体或模式,如在用户行为分析、市场细分等领域。 **5. 数学与统计工具:** Mahout提供了基础的数学和...
2. **聚类(Clustering)**:如K-Means、Fuzzy K-Means和Canopy Clustering,用于将数据点自动分组到相似的集合中,无监督学习的一种常见应用。 3. **协同过滤(Collaborative Filtering)**:这是推荐系统的基础,...
2. **聚类**:包括K-Means、Fuzzy K-Means和Canopy Clustering等算法,可以对数据集进行无监督学习,将相似的数据点分组到一起,形成不同的簇。 3. **分类**:支持如Naive Bayes和Random Forest等监督学习算法,...
例如,clustering_material.txt文件可能包含有关Mahout中聚类算法的详细资料,如K-Means、Fuzzy K-Means、Canopy Clustering等。 K-Means是一种迭代的聚类算法,通过不断调整每个数据点所属的类别中心来优化结果。...
Mahout提供了多种聚类算法,包括K-means、Fuzzy K-means、Canopy Clustering和DBSCAN等。其中,K-means是最常见的,用于将数据点分配到最近的聚类中心。Fuzzy K-means允许数据点属于多个簇,而Canopy Clustering是一...
- **聚类(Clustering)**: 包括K-Means、Fuzzy K-Means、Canopy Clustering等算法,用于将数据无监督地分组到相似的集合中。 - **推荐系统(Recommender Systems)**: Mahout支持基于用户和物品的协同过滤,以及...
3. **聚类算法**:如K-Means、Fuzzy K-Means、Canopy Clustering,用于将相似的数据点分组到不同的簇中。这在市场细分、社交网络分析和图像处理中有重要作用。 4. **矩阵分解**:如SVD(奇异值分解)和ALS(交替...
1. **聚类**:Mahout提供了多种聚类算法,如K-means,Fuzzy K-means,和Canopy Clustering等。这些算法用于将数据集中的对象分成不同的组或簇,使得同一簇内的对象相似度较高,而不同簇之间的对象相似度较低。这对于...
- 聚类算法的应用:聚类是一种无监督学习方法,Mahout实现了诸如K-means、Fuzzy K-means、Canopy等聚类算法。书籍中通过实例教授如何对数据集进行聚类分析。 - 推荐系统的构建:推荐系统是电子商务和内容推荐等领域...
聚类算法如K-Means、Canopy聚类、模糊K-Means等在Mahout中得到了实现。这些算法可以帮助用户从大量未标记的数据中发现有意义的结构,对于市场细分、社交网络分析等应用非常有用。 本书《Mahout in Action》于2012年...