基于云平台的层次聚类算法在煤炭产业中的应用.pdfVIP

收稿日期:2013 05 10;修订日期:2013 08 28 作者简介:张海建（1978 ），男，北京人，讲师，硕士，研究方向：计算机软件，数据库系统。 0 引言 聚类算法在数据挖掘、机器学习等领域得到了广泛地应 用。聚类可以挖掘出潜在的类簇群体，从而针对不同的类簇 群体进行深入挖掘分析。在煤炭产品分析、研究方面，煤炭产 业也开始逐步地引入数据挖掘领域中的聚类分析算法，利用 聚类分析算法可以有效地聚集不同的煤炭产品，并能有效地 对不同类簇产品产生相对应的销售方案以及不同的营销策 略。聚类分析算法是指把相似的对象通过静态分类的方法分 成不同的组别或者更多的子集（subset），这样让在同 1个子集 中的成员对象都有相似的一些属性，其中，常见的包括在坐 标系中更加短的空间距离等。随着聚类算法的研究，层次聚 类分析算法在各个领域得到了逐步地引入及应用。层次聚类 算法是把相似的对象通过静态分类的方法分成不同的组别 或者更多的子集（subset），这样让在同 1个子集中的成员对 象都有相似的一些属性，常见的包括在坐标系中更加短的空 间距离等。 层次聚类算法需要计算不同样本之间的相似性， 即相似性矩阵。随着数据规模的增大，煤炭产业不能有效地 利用传统的层次聚类算法完成有效地聚类分析工作。文章针 对海量规模的煤炭产品相关数据完成聚类分析工作问题，提 出了基于 MapReduce分布式计算框架的分布式层次聚类算 法，该算法能够高效、分布式地完成相似性矩阵的计算，以及聚 类分析工作。通过大量的实验结果也进一步证明了文中提出的 基于云平台的层次聚类算法具有很高的效率以及可扩展性。 1 层次聚类算法简介 层次聚类算法包括最短距离法、最大距离法以及 K平均 距离算法。文中是基于最短距离法进行改进的。下面，对基于 最短距离法的层次聚类算法进行详细地介绍。 （1）假设有 N个样本的集合 T={T 1 , T 2 , ..., T N }； （2）规定想要生成的聚类个数为 K； （3）计算不同样本之间的距离，完成相似度矩阵的计算， 距离的计算公式如下： d ij = （f i1 -f j1 ） 2 +（f i2 -f j2 ） 2 +…+（f in -f jn ） 2 姨 d ij 表示为样本 i 和 j 之间的距离； f ik 表示样本 i 的第 k 个属 性的值； （4）计算距离公式计算完成后，从距离中选择距离最近 的 2个样本，将该 2个样本归为一类； （5）聚类完成后，更新不同类别之间的距离，当 1个类别 中包含多个样本的情况下，类别之间的距离定义为不同类别中 样本之间最近距离；即，距离定义为如下： d(c i ,c j )= min x∈c i y∈c j d xy 其中， d (c i ,c j ) 表示类别 c i ,c j 之间的距离 ；x，y表 示为在类别 c i ,c j 中的样本。 基于云平台的层次聚类算法在煤炭产业中的应用 张海建 （北京信息职业技术学院， 北京 100018） 摘 要:层次聚类（Hierarchical Clustering）就是通过对数据集按照某种方法进行层次分解。该聚类方法可以设定聚 类的个数，并得到了各个研究和应用领域的广泛应用。煤炭产业中往往希望对煤炭的产品进行聚类分析，从而有助 于开发和生产。随着煤炭系统中收集的煤炭数据数量的增多，层次聚类算法由于需要计算大量的相似性矩阵需要 大量的内存，原有的层次聚类算法不能有效地处理海量规模数据。文章针对煤炭数据中生成的大规模数据，提出基 于云计算平台的分布式层次聚类算法，该算法能够分布式完成相似性矩阵的保存和计算，快速、准确地完成层次聚 类工作。在实验部分通过 2组实验证明了算法具有很高的效率以及很高的可扩展性。 关键词:层次聚类； 云平台； 煤炭产业； 大规模数据 中图分类号:TP301 文献标识码:A 文章编号:1008 8725（2013）12 0194 03 Application of Hierarchical Clustering Algorithm in Coal Industry Based on Cloud Platform ZHANG Hai-jian （Beijing Information Technology College, Beijing 100018, China） Abstract:Hierarchical clustering is the decomposition of data following some methods. This clustering algorithm can set the number of clusters, and it is widely applied in several areas.