聚类k.means算法与并行化.研究

《聚类k.means算法与并行化.研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、重庆大学硕士学位论文1绪论试多种算法，以便发现数据可能隐含的所有规律与知识。K-means属于聚类分析中一种基本的划分方法，常采用误差平方和准则函数作为聚类准则。主要优点是算法简单、快速而且能有效地处理大数据集。然而这种算法依赖于初始值的选择以及数据的输入顺序。此外，由于运用误差平方和准则函数测度聚类效果，如果各簇的形状和大小差别很大，为使误差平方和血值达到最小有可能出现将大的聚类簇分割的现象。论文针对K-means算法采用准则函数衡量聚类质量存在的局限性以及对初值的依赖性，基于多次取样一次聚类寻找摄优初值的思想提出了一种新改进的K—means算法，实

2、验结果表明，该算法聚类效果优于原始算法并具有较好的稳定性。同时还研究了如何在性能／价格比较高的机群系统上实现K～means算法的并行，以提高聚类的执行效率。因此，本课题具有实用价值和理论意义。1．2国内外聚类方法现状综述1．2．1聚类简介在统计方法中，聚类又称聚类分析，它是多元数据分析的三大方法之一(其它两类是回归分析和判别分析)。它主要研究基于几何距离的聚类，如欧式距离、明考斯基距离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类，需要考察所有的个体才能确定

3、类的划分：因此它要求所有的数据必须预先给定，不能动态地增加新的数据对象。聚类分析方法不具有线性的计算复杂度，难以适用于数据库非常大的情况。聚类分析问题可描述为：给定聊维空间月“中的竹个向量，把每个向量归属到S聚类中的某一个，使得每个向量与其聚类中心的“距离”最小。聚类分析问题实质上是一个全局最优问题。在这里，m可视为向量参与聚类的属性个数，”是向量的个数，S是由用户预先设定的分类数目。定义对于聊维空间R”中的向量X{，XJ，Xi=毯n，X∞⋯，X№＼，Xi=诳”X谊，⋯，X№＼，向量x，，x，之间的距离为：dtj=、／∑k—Xjk_)2Yk=l聚类与数

4、据挖掘中的分类不同。分类问题中，已知训『练样本数据的分类标记提炼学习规则，在测试准确性后用以确定新数据所属类别；而聚类分析的输入数据集是一组不含类标记的对象，即输入的数据对象没有被进行任何分类，聚类的目2重庆大学硕士学位论文】绪论的是根据一定的规则，合理地进行数据分组或聚类，并以显式或隐式的方法描述聚类结果。由于在具体分析过程中可以采用不同的算法，所以对于相同的数据集合可能有不同的划分。在机器学习中，聚类是无指导学习的一个例子，分类是有指导学习的一个例子，两者所采用的方法相差甚远，并且聚类的时间复杂度一般比分类大。聚类的用途是很广泛的。在商业上，聚类可

5、以帮助市场分析人员从他们的消费者数据库中区分出不同的消费群体，并概括出每一类消费者的消费模式，可以从保险公司的数据库中发现汽车保险中具有较高索赔概率的群体；在生物学中，它可以被用来辅助研究动、植物的分类，可以对具有相似功能的基因进行分类，还可以用来发现人群中的一些潜在的结构等等；聚类还可以用来从地理数据库中识别出具有相似土地用途的区域。1．2．2聚类方法的分类聚类方法大体可以划分为以下几类：划分的方法、层次的方法、基于样本分布密度的方法，基于空问网格的方法以及基于类模型的方法。(1)划分的方法：给定一个包含玎个数据对象的数据集，一个划分算法构建数据的k

6、个划分，每个划分表示一个类，并且k≤n。通常算法中会采用一个划分准则(称为相似度函数)，例如距离，以便在同一个簇中的对象是“相似的”，在不同簇中的对象是“相异的”。K-means算法是最广泛应用的一种基于目标函数的划分聚类方法，一般都采用梯度法求解极值，由于梯度法的搜索方向总是沿着能量减小的方向进行，因此容易陷入局部极小值。当结果簇密集并且各簇之间的区别明显时，采用该算法效果较好。(2)层次的方法：层次的算法对给定的数据对象集合进行层次化的分类。根据层次的分解形成方式，可以分为两种：自底向上的凝聚法和自顶向下的分裂法。凝聚法一开始将每个数据对象自身看成

7、一个类，然后相继地合并相近的数据对象或类，直到所有的类合并为一个(最顶层)或者满足某个终止条件。分裂法一开始将所有数据对象视为同一个类，在迭代的每一步中，将当前层的每一个类分为更小的类，直到每个对象各自单属一个类或者满足某个终止条件。(3)基于密度的方法：绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而难以发现任意形状的簇。随之提出了另～种聚类方法——基于密度的方法。其主要思想是：只要临近区域的密度(对象或数据点的数目)超过某个阈值就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中至少包含某个数目的点。这样的

8、方法可以用来过滤“噪声”数据，发现任意形状的簇。(4)基于网格的方法：基于网格的方法把对象空间