数据流聚类算法研究（精选9篇）
数据流聚类算法研究 篇1
1 相关概念
1.1 数据挖掘
数据挖掘就是从大量、不完全、有噪声、模糊、随机的数据中, 提取隐含在其中、人们事先不知道、但又是潜在有用的信息和知识的过程。很多术语与其相近似, 如从数据库中发现知识、数据分析、数据融合以及决策支持等。人们把原始数据看作是形成知识的源泉。发现知识的方法可以是数学的, 也可以是非数学的;可以是演绎的, 也可以是归纳的。发现的知识可以被用于信息管理、查询优化、决策支持、过程控制等, 还可以用于数据自身的维护。因此, 数据挖掘是一门广义的交叉学科, 它汇聚了不同领域的研究者, 尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。
1.2 聚类算法
将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类。聚类算法是数据挖掘的核心技术。聚类与数据挖掘中的分类不同, 在分类模块中, 对于目标数据库中存在哪些类这一信息是已知的, 要做的就是将每一条记录分别属于哪一类标记出来。聚类与此相似但又存在不同, 它是在预先不知道目标数据库到底有多少类的情况下, 希望将所有的纪录组成不同的类或者说“聚类”, 并且使得在这种分类情况下, 以某种度量为标准的相似性, 在同一聚类之间最小化, 而在不同聚类之间最大化。事实上, 聚类算法中很多算法的相似性都是基于距离的, 而且由于现实数据库中数据类型的多样性, 关于如何度量两个含有非数值型字段的记录之间的距离的讨论很多, 并提出了相应的算法。在很多应用中, 由聚类分析得到的每一个聚类中的成员都可以被统一看待。聚类分析的算法可以分为以下几大类:分裂法、层次法、基于密度的方法、基于网格的方法以及基于模型的方法等。
2 聚类算法设计与实现
2.1 聚类算法总体思想
单重系统聚类的基本思想是, 先将n个样品各自看成一类, 然后计算各类两两之间的距离, 选择其中距离最小的两类合并成一个新类, 于是n类样品就聚成了n-1类, 计算这一新类与其他各类之间的距离, 再合并其中距离最小的两类, 如此反复进行, 每次减少一类, 直到所有样品归为一类。
传统系统聚类是一种基于全局比较的聚类, 它不具有线性的计算复杂度, 因此难以使用于数据库非常大的情况, 尤其当被考察样本的指标个数多时, 其准确性很难得到保证。本文提出的多重系统聚类算法是对传统系统聚类算法的一种改进, 它克服了样本数据中不同类型指标之间缺乏比较规则的缺点, 适合于对大量数据、多指标样本的聚类分析。
本文的设计是按照系统聚类方法实现的多重系统聚类挖掘的算法。在实现该算法时, 为了加以比较, 按照聚类样本的数据阵的不同分为两部分, 初始样本数据阵都是一样的, 都是输入的记录数组, 以这个初始的数组先进行单重聚类, 之后再进行多重聚类。
2.2 算法详细设计
在此算法中主要应用三个函数, 它们的功能和实现如下:
(1) Cluster_else () 函数
此函数主要进行聚类操作, 在此函数中, 为了标号数组能够按照从小到大的顺序存储聚类后的标号, 定义了二维数组ss存储每一次聚类后的数组下标, ss数组中每一行的数值就是每最终聚成一类的各项的下标, 然后调整每一行, 使得每一行的最小值在每一行的第一个元素。再对每一行的第一个元素按照从小到大的顺序进行冒泡排序并按顺序调整各行的值。最后以ss数组中的值为标号数组的下标, 对标号数组中下标为ss中第一行开始从1开始赋值一直到聚类的最终类别数。
(2) Cluster () 函数
此函数主要是完成最终的多重聚类操作并且聚类的最终结果在此函数中输出, 设置变量n为判断循环条件的变量, N为样本数据阵的行数, 也就是样品的样本数。k为输入的聚类的类别数。同样每做一次循环, n就减1, 当n值不再小于固定的k值时, 结束循环。因为此函数除了要进行聚类外, 还要把聚类后无序的结果表示出来。
(3) sq () 函数
此函数为计算空间两点间距离的函数, 假设有空间中两点, 其坐标分别为P (x1, y1, z1) 、Q (x2, y2, z2) , 则空间中这两点的距离公式为:
此函数为一个有返回值的函数, 返回值是各坐标之差平方的和, 在调用这个函数的程序中, 按照距离公式的要求, 要想求出空间两点的距离, 还应对这个返回值进行开根号处理, 才能得到最后的空间两点间的距离。
在主函数main () 的设计中, 主要按照多重聚类的思想, 先对子空间进行分类, 设计的分类原则是按照第一个样本所有属性的值进行从小到大的排序, 然后相邻的两列属性值被划分成一个子空间, 如此, 如果每一个样品有14个属性, 则划分为7个子空间, 如果有15个属性, 为单数, 则最后一列属性单独为一个子空间进行聚类操作。同时每一个子空间进行聚类操作后都会改变样本数据阵的值, 在Cluster_else函数中将每一次聚类后的结果合并到一个数组中, 在再次进行聚类时, 这个数组中的元素作为样本数据阵的值进行多重聚类。
2.3 算法实现
在运行程序进行验证之前, 先对样本数据阵进行赋值操作:对A、B、C、D……P等代表16个不同城市的13个地理属性值进行赋值。各属性的赋值情况如图1所示。
按照多重聚类算法的思路, 在输入数据时, 要将最重要的样本放在第一类别的位置上。暂时认为A城市为中心城市, 在聚类的第一项上, 然后进行聚类操作。聚类时先做子空间的划分, 以第一类的各属性值为主进行从小到大的冒泡排序, 并调整数矩阵, 相邻的两个属性值所在的列划分为一个子空间, 接收对子空间聚类的类别数9;对每一个子空间都聚成9类, 然后将结果的数据阵用两种方法分别合到一个矩阵中。接收最终聚类的类别数7;分别对合到一起的矩阵进行聚成7类的聚类操作, 并输出最终结果。图2是在VC中运行此算法所显示聚类结果的界面。
从图2可以看出, 使用不同的样本数据阵的值进行聚类的结果是完全不一样的, 因为按属性值进行聚类操作时, 用来聚类的样本数据阵的值是根据输入大小不一的、无序的属性值聚类的结果所调整的。并且每一次聚类都要将距离最小的两类聚到一起, 因为样本数据的无序性和大小差别很大的特点, 在聚类的类别数要求很大时就容易造成大部分的样品聚成了一类, 因为在上一次聚类中那些为一类的样品距离是最小的, 很容易在下一次聚类时它仍然是要被聚在一起的两类中的一类, 所以按属性值进行聚类的结果很容易“聚堆”。而按照类别标号进行聚类的结果就不容易出现上述情况, 因为, 按类别标号进行聚类的操作时, 它的样本数据阵是代表类别的标号, 是从1到N的正整数, 这些数之间是有序的, 并且大小差别不大, 所以在聚类后的结果中能够充分显示出聚类的类别, 无论要求聚成的类别数是大是小, 它都能充分的显示出来。
3 结论
基于统计的系统聚类算法解决了一些原有的系统聚类算法可能遇到的难题, 比如:在实际中, 单纯的样本聚类因为忽视了不同指标间也存在一定的关系而使得有时聚类结果并不准确的问题, 用户可自行设计对子空间的聚类的类别数和总的类别数等。本文介绍的方法还存在一些不足:
首先是子空间划分的粒度问题, 多重聚类建立在对包含某一类指标的样品分别聚类结果的基础上, 最后结果的准确性与指标的划分有着直接关系;其次是对首次聚类结果的排序问题, 因为不同指标的衡量规则不同, 所以聚类的结果往往缺乏一定的可比性, 很有必要找到一种统一的规则对这个结果作一个排序;最后, 没有给出算法更严格的时间复杂度的分析, 有关效率的分析都是实际运行测试和比较的结果, 这部分工作对于一个算法的完整性以及算法应用的推广都是必不可少的。
摘要：聚类算法是数据挖掘的核心技术。研究了一种多重系统聚类模型及其算法实现, 将变量聚类和样本聚类结合起来, 先将指标按一定的规则分成若干类别, 然后对包含每一类别指标的样本数据分别进行聚类, 使用这种多重聚类方法, 分类性能有了较大提高。并且在此算法多重聚类的实现中, 使用了两种方法赋值样本数据阵, 使聚类的结果有了直观的比较。
关键词：系统聚类,数据挖掘,知识发现
参考文献
Jiawei Han, Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社, 2001.
张红云, 刘向东, 段晓东, 等.数据挖掘中聚类算法比较研究[J].计算机应用与软件, 2003 (2) :5-6.
陈伟鹤, 殷新春, 张锐, 等.数据挖掘对数据库安全的影响[J].计算机科学, 2003 (1) :70-71.
R L Scheier.Finding pearls in an ocean of data[J].Computer-world, 2001, 35 (30) :49-50.
Neana Buck.Eureka!knowledge discovery[J].softwareManazine, 200-12/2001-01, 20 (6) :24-29.
聚类算法研究综述 篇2
关键词：数据挖掘；聚类分析；聚类算法
中图分类号：TP301. 6 文献标识码：A文章编号：1009-3044(2007)12-21500-02
The Research of Clustering Algorithms
XIANG Bing-bing1, QIAN Guang-chao2
(1.School of Mathematics and Computational Science, Anhui University, Hefei, Anhui Province 230039, China；2. School of Computer Science and Technology ,Anhui University, Hefei, Anhui Province 230039, China)
Abstract：Clustering is an important technique in data mining. It’s used to discover the data distribution and concealed patterns. The paper elucidate the basic principle of the clustering algorithms and sum up the contemporary research of the clustering algorithms. It also analyze a few representative clustering algorithms and compare their differences，advantages and disadvantages. At last，the paper indicate the development trend of clustering integrating the application demand.
Key word:Data mining； Clustering Analysis；Clustering Algorithms
1 引言
数据挖掘是指从从大量无序的数据中提取隐含的、有效的、可理解的、对决策有潜在价值的知识和规则，为用户提供问题求解层次的决策支持能力。数据挖掘主要的算法有分类模式、关联规则、决策树、序列模式、聚类模式分析、神經网络算法等等。聚类算法是一种有效的非监督机器学习算法，是数据挖掘中的一个非常重要的研究课题。当人们使用数据挖掘工具对数据中的模型和关系进行辨识的时候，通常第一个步骤就是聚类，其目的就是将集中的数据人为地划分成若干类, 使簇内相似度尽可能大、簇间相似度尽可能小，以揭示这些数据分布的真实情况。但任何聚类算法都对数据集本身有一定的预先假设，根据文献[1]的理论，如果数据集本身的分布并不符合预先的假设，则算法的结果将毫无意义。因此，面对特定的应用问题，如何选择合适的聚类算法是聚类分析研究中的一个重要课题。本文比较了数据挖掘中现有聚类算法的性能，分析了它们各自的优缺点，并指出了其今后的发展趋势。
2 聚类算法分类研究
聚类的目的是把大量数据点的集合分成若干类，使得每个类中的数据之间最大程度地相似，而不同类中的数据最大程度地不同。通常聚类算法可以分为层次聚类、分割聚类、密度型聚类、网格型聚类和其他聚类等几种。
2.1 层次聚类
层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类，它又可以分为两类，即自底向上的聚合层次聚类和自顶向下的分裂层次聚类。聚结型算法采用自底向上的策略， 首先把每个对象单独作为一个聚类， 然后根据一定的规则合并成为越来越大的聚类， 直到最后所有的对象都归入到一个聚类中。大多数层次聚类算法都属于聚结型算法， 它们之间的区别在于类间相似度的定义不同。与聚结型算法相反， 分裂型算法采用自顶向下的方法，它先将所有的对象都看成一个聚类，然后将其不断分解直至每个对象都独自归入一个聚类。一般情况下不使用分裂型方法， 因为在较高的层次很难进行正确的拆分。纯粹的层次聚类算法的缺点在于一旦进行合并或分裂之后， 就无法再进行调整。现在的一些研究侧重于层次聚类算法与循环的重新分配方法的结合。
主要的层次聚类算法有BIRCH， CURE， ROCK， CHAMELEON， AMOEBA，COBWEB， Clustering with Random Walks 算法等。CURE算法[2]不用单个中心或对象来代表一个聚类，而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类，这样就可以识别具有复杂形状和不同大小的聚类，从而能很好地过滤孤立点。ROCK算法[3]是对CURE的改进，除了具有CURE算法的一些优良特性之外，它还适用于类别属性的数据。CHAMELEON算法[4]是Karypis等人于1999年提出来的，它在聚合聚类的过程中利用了动态建模的技术。
2.2 分割聚类
分割聚类算法是另外一种重要的聚类方法。它先将数据点集分为k个划分，每个划分作为一个聚类，然后从这k个初始划分开始，通过重复的控制策略，使某个准则最优化，而每个聚类由其质心来代表( k- means 算法) ， 或者由该聚类中最靠近中心的一个对象来代表( k- medoids 算法)，以达到最终的结果。分割聚类算法收敛速度快，缺点在于它倾向于识别凸形分布大小相近、密度相近的聚类，不能发现分布形状比较复杂的聚类，它要求类别数目k 可以合理地估计， 并且初始中心的选择和噪声会对聚类结果产生很大影响。这类方法又可分为基于密度的聚类、基于网格的聚类等。
很多算法中都使用距离来描述数据之间的相似性，但是，对于非凸数据集，只用距离来描述是不够的。对于这种情况，要用密度来取代相似性，这就是基于密度的聚类算法。基于密度的算法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可以发现任意形状的类。此类算法除了可以发现任意形状的类，还能够有效去除噪声。
基于网格的聚类算法，把空间量化为有限个单元( 即长方体或超长方体) ，然后对量化后的空间进行聚类。此类算法具有很快的处理速度。缺点是只能发现边界是水平或垂直的聚类，而不能检测到斜边界。此类算法具有很快的处理速度。时间复杂度一般由网格单元的数目决定， 而与数据集的大小无关。此外，聚类的精度取决于网格单元的大小。此类算法不适用于高维情况，因为网格单元的数目随着维数的增加而呈指数增长。所有基于网格的聚类算法都存在下列问题：一是如何选择合适的单元大小和数目；二是怎样对每个单元中对象的信息进行汇总。
主要的分割聚类算法有k - means， EM， k - medoids， CLARA， CLARANS 等。常见的k -medoids 算法有PAM算法、CLARA 算法、CLARANS 算法。
2.3 其他聚类
主要有：基于约束的聚类算法、机器学习中的聚类算法、用于高维数据的聚类算法等。
基于约束的聚类算法，其约束可以是对个体对象的约束，也可以是对聚类参数的约束，它们均来自相关领域的经验知识。该方法的一个重要应用在于对存在障碍数据的二维空间数据进行聚类。COD (Clustering with Obstructed Distance) [ 5]就是处理这类问题的典型算法，其主要思想是用两点之间的障碍距离取代了一般的欧氏距离来计算其间的最小距离。
机器学习中的聚类算法是指与机器学习相关、采用了某些机器学习理论的聚类方法，它主要包括人工神经网络方法以及基于进化理论的方法。如自组织特征映射( SOM) 网络是利用人工神经网络进行聚类的较早尝试，它也是向量量化方法的典型代表之一。在基于进化理论的聚类方法中，模拟退火的应用较为广泛， SNICC算法[ 6 ]就是其中之一。遗传算法也可以用于聚类处理，它主要通过选择、交叉和变异这三种遗传算子的运算以不断优化可选方案从而得到最终的聚类结果。
高维数据聚类是目前多媒体数据挖掘领域面临的重大挑战之一，除了降维这一最直接的方法之外，对高维数据的聚类处理还包括子空间聚类以及联合聚类技术等。子空间聚类算法，认为在高维数据集中，聚类往往不是存在于整个空间中，而是存在于某些子空间中。它们针对高维空间数据，寻找子空间中的聚类。主要子空间聚類算法有CLIQUE，PROCLUS 等。
3 典型聚类算法性能比较
3.1 CLARANS 算法
CLARANS通过利用多次不同抽样改进了CLARA算法，是一种k-中心点聚类方法。它首先随机选择一个点作为当前点，然后随机检查它周围不超过参数Maxeighbar个的一些邻接点。假如找到一个比它更好的邻接点，则把它移入该邻接点，否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量，直至所找到的局部最小量数目达到用户要求为止。该算法要求聚类的对象必须预先调入内存，并且需多次扫描数据集，其时空复杂度都相当大，虽通过引入R*—树结构对其性能进行改善，但构造和维护代价太大。该算法对脏数据和异常数据不敏感，但对数据输入顺序异常敏感，且只能处理凸形或球形边界聚类，效率较高。
3.2 BIRCH 算法
BIRCH是一个综合性的层次聚类方法，它利用层次方法的平衡迭代进行归约和聚类。其核心是用一个聚类特征三元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法具有对象数目的线性易伸缩性，及良好的聚类质量。一次扫描就可以进行较好的聚类，其计算复杂度为O( n)。BIRCH 算法只适用于类的分布呈凸形及球形的情况，对不可视的高维数据则是不可行的。
3.3 DBSCAN 算法
DBSCAN是基于密度的聚类算法，可以将足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的聚类。该算法利用类的密度连通性可以快速发现任意形状的类。其基本思想是：对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目。DBSCAN算法不进行任何的预处理而直接对整个数据集进行聚类操作。当数据量非常大时，就必须有大量内存支持，I/O 消耗也非常大。其时间复杂度为O(nlogn)，聚类过程的大部分时间用在区域查询操作上。DBSCAN算法能够发现空间数据库中任意形状的密度连通集；在给定合适的参数条件下，能很好地处理噪声点；对用户领域知识要求较少；对数据的输入顺序不太敏感；适用于大型数据库。但DBSCAN算法要求事先指定领域和阈值，具体使用的参数依赖于应用的目的。
3.4 STING 算法
STING 是一种格的多分辨率聚类技术。它将空间区域划分为矩形单元，针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易地从低层单元的计算得到。STING扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O (n) ，其中n是对象的数目。在层次结构建立后，查询处理时间是O ( g)，g是最低层风格单元的数目，通常远远小于n。
STING 是独立于查询的，有利于并行处理和增量更新且效率较高。但由于STING 采用了一个多分辨率的方法来进行聚类分析，聚类的质量取决于网格结构的最低层粒度。如果数据粒度比较细，处理的代价会明显增加。并且，STING 在构建一个父单元时没有考虑子单元和其相邻单元之间的关系，因此，尽管该技术处理速度快，但可能降低簇的质量和精确性。
4 结论和展望
聚类分析是数据挖掘中一种非常有用的技术，它可作为特征和分类算法的预处理步骤，也可将聚类结果用于进一步关联分析，还可以作为一个独立的工具来获得数据分布的情况。聚类算法的研究具有广泛的应用前景，其今后的发展也面临着越来越多的挑战。首先是聚类算法的选择，建议使用者根据实际情况(例如发现聚类的形状、数据输入顺序是否敏感、适用数据库的大小或者算法效率)来选择合适的聚类算法。其次，对于特征数据本身所具备的高维性、复杂性、动态性以及容易达到大规模的特性，聚类算法的设计还应该更多地考虑融合不同的聚类思想形成新的聚类算法，从而综合利用不同聚类算法的优点。
参考文献：
[1]R O Duda，P E Hart，D G Stork. Pattern Classification ( 2nd Edition) [M]. New York: Wiley， 2001. 4542458.
[2]Guha S， Rastogi R，Shim K. CURE: An Efficient Clustering Algorithm for Large Databases[C]. Seattle: Proceedings of the ACM SIGMOD Conference，1998. 73-84.
[3]Guha S，Rastogi R，Shim K. ROCK: A Robust Clustering Algorithm for Categorical Attributes[C]. Sydney: Proceedings of the 15 th ICDE，1999. 512-521.
[4]Karypis G，Han E-H，Kumar V. CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling[J]. IEEE Computer，1999，32 (8) : 68-75.
[5]Tung A K H，Hou J，Han J. Spatial Clustering in the Presence of Obstacles[C]. Heidelberg: Proceedings of the 17 th ICDE，2001. 359-367.
数据流聚类算法研究 篇3
随着信息技术和电子商务的飞速发展,数据正以惊人的速度剧增,无论是数据量还是数据种类都越来越丰富。这些海量的数据中隐藏着大量有价值的信息,如何存储、处理这些海量数据,从这些海量数据中挖掘出有用信息,利用已有数据进行预测是目前的研究热点。
海量数据分布在不同 的计算机 中,分布式计 算和大规模异构系统 资源共享 是实现海 量数据挖 掘的关键 技术,云计算技术为这一问题提供了理想的技术解决方案,云计算平台满足了用户“按需使用,按量付费,即需即用”的服务需求,有效解决了计算 机中海量 数据的存 储与处理问题。
1云计算
1.1云计算概念
云计算(CloudComputing)是将存储 于电脑、移动 电话和智能通讯设备上的大量信息和处理器资源集中在一起进行工作的超级计算机模式。它将要完成的任务分布在大量计算机构成的资源池上,各种应用系统能够根据需要从资源池中获取计算力、存储空间和各种软件服务[1]。
云计算是集群计算(ClusterComputing)、分布式处理(DistributedComputing)、并行计算(ParallelComputing)和网格计算(GridComputing)的发展[2]。云计算采 用计算机集群构成数据中心和资源池,使用户能够利用互联网随时随地、按实际需要共享云资源。
1.2云计算特点
云计算以其超大规 模、高可扩展 性、高可靠性、虚 拟化、按需分配、廉价性和通用性等优势,使普通用户在普通计算机上都能享受到高性能计算机的存储、计算能力,给人类生活和工作带来了极大便利。目前Google、IBM、Microsoft等大型互联网企 业都部署 有云计算 平台,供用户分享云技术带来的好处。
1.3云计算平台
云计算系统主要由云平台、云终端、云存储和云安全4部分组成,其中云平台是云计算系统的核心,它整合了多个数据中心的资源,统一分配和调度计算机资源、存储资源和网络资源,为用户提供了良好的计算环境、开发平台和应用软件等多种服务[3]。
云计算平台可以划分为存储型云平台、计算型云平台以及综合云计算平台。其中,存储型云平台主要以数据存储为主,计算型云平台主要进行数据处理,综合云计算平台则兼顾计算和数据存储。
Hadoop是一个易开发及并行处理海量数据的云计算平台,主要由两部 分组成:分布式文 件系统HDFS(HadoopDistributedFileSystem)和MapReduce计算模型[4,5],HDFS为海量数 据提供存 储,是分布式 计算的基石,采用了M/S架构,主要执行的操作有创建、删除、移动或重命名等,架构类似 于传统的 分级文件 系统;而MapReduce则为海量数据提供计算。
2数据聚类分析
聚类分析(ClasteringAnalysis)以对象的相似性为基础,在聚类模式之间具有更多的相似性,是数据挖掘的重要技术之一。聚类是将物理或抽象对象的集合分成由类似的对象组成多个类的过程,是现实世界中普遍存在的现象,作为统计学的一个分支,其应用非常广泛。
在数据挖掘之前,对象类划分的数据量与类型均是未知的,因此在数据挖掘后一般需要对数据挖掘结果进行合理的分析与解释。聚类算法可分为划分法、层次法、基于网格方法、基于密度方法、图论聚类法等。数据聚类分析主要有4个步骤,如图1所示。
3基于 Hadoop的数据聚类算法
数据挖掘的特点就是从海量数据中提取有价值的规则和信息。随着数据量和种类的急剧增加,传统的数据挖掘技术已经很难满足数据挖掘的需求。在云计算时代,海量的数据分布在不同地理位置的计算机上,现有聚类算法在时间复杂性和空间复杂性上都无法很好地解决此问题。研究思路就是将并行处理技术应用到现有的聚类算法中,降低聚类算法的时间 复杂度和 空间复杂 度,节约聚类 时间。
并行聚类算法能够在多台计算机上同时运行,满足云计算需求,节约了大量计算机资源。目前,并行聚类算法有:并行聚类算法PWIDE、并行K-Means算法、基于密度和密度可达并行聚类算法PCADD等[6]。
K-Means算法是最 著名和最 常用的聚 类算法。Kmeans算法以k为输入参数,把n个对象分为k个簇,使得簇内具有较高的相似度,簇间具有较低的相似度。相似度的计算根据一个簇中对象的平均值(被称为簇的重心或簇心)进行。本文聚类 算法采用 均方差作 为标准测 度函数:
其中,E为所有数据对象的均方差之和;P代表对象空间中的一个点;mi为聚类均值。
并行K-means算法采用 数据并行 的设计思 想,首先把整个空间数据按照计算机的节点数量对海量的数据集X进行划分,形成N个子数据样本集X1,X2,X3……XN(N为计算机节点个数),每个节点上分别对应自己的数据集,然后对每个子数据集进行独立的数据聚类,形成数据集的簇{C11,C12,……,C1M},{C21,C22,……,C2O},……,{Cn1,Cn2,……,CnQ}(其中M,O,Q为聚类簇的个数,N为数据集的个数),最后把聚类结果发送到主节点上,主节点再把各个聚类结果汇总,输出最终的聚类结果。
Hadoop平台主要有HDFS和MapReduce两部分,并行K-means聚类算法,在每次迭代过程 中分别执 行Map和Reduce操作。
在Hadoop平台中,HDFS负责存储 海量数据,并管理数据文件,记录数据文件分布在哪个节点上,从哪个数据节点上获得,并记录数据的初始中心。Map函数的任务是完成每个记录员到中心点距离的计算并重新标记其新的类别,其输入为待聚类所有数据和上一轮聚类中心,输入数据聚类 < 行,记录 >。Reduce函数的任 务是根据Map函数得到的中间计算结果,计算出新 类的聚类 中心并发送给各节点,更新HDFS到文件然 后进行下 一次迭代直到收敛。
并行K-means聚类算法步骤如下:1任意选择K个样本作为初始的中心点;2迭代并执行Map和Reduce操作;3直到收敛。
4结语
数据流聚类算法研究 篇4
摘要：针对一致聚类算法中聚类数目判断不准确、聚类速度慢等问题，通过集成复杂网络中的Newman贪婪算法与谱聚类算法，提出了一种新的基于Minkowski距离的一致聚类算法。该算法利用Minkowski距离刻画样本间的相似度，根据随机游走策略，结合不同数据的特征值分布分析方法进行聚类，实现聚类数目的自动识别。实验仿真说明算法具有较少的运算时间及较高的聚类精度。结合实际铜矿泡沫浮选过程特点，将该算法应用于浮选工况分类，进一步验证了算法的有效性。
关键词：一致聚类；Minkowski距离；一致矩阵；聚类数目；工况识别
中图分类号：TP273 文献标识码：A
聚类分析作为一种有效的数据处理方法，在复杂工业工程中得到了广泛关注。近年来涌现出了多种聚类分析方法，包括层次聚类算法、划分式聚类算法（如K-modes-Huang算法等）、基于网格和密度的聚类算法（如网格密度等值线聚类算法、基于移位网格概念的密度和网格的聚类算法SGCE）等。这些聚类方法在多个领域得到广泛应用，其理论也得到不断的丰富和发展。
但是对不同结构特征的数据进行聚类分析时，现有的聚类方法遇到了难题，如相似度矩阵的选取问题、聚类数目的自动确定等。而一致聚类方法的提出，成为解决聚类问题的一种重要分析方法。该方法也称作聚类集成或划分算法，即针对某一特定的数据获得多种数目的不同聚类结果，并从中选取最能反映聚类信息的类别。在确定聚类数目方面，一致聚类方法具有特色，并为基因微阵数据、文本数据等聚类问题的解决提供了很好的思路。由于聚类过程中聚类数目的判断标准不尽相同，适用的领域也不同，其中最具有代表性的两种一致聚类方法是结合重采样或交叉验证等技术的一致聚类方法和基于迭代的一致聚类方法。但这两种一致聚类算法也存在聚类数目识别不准确等问题，主要是源于其重采样方法中最优的采样次数及迭代方法中的迭代次数不能有效且最优设定。
本文提出了一种新的基于Minkowski距离的一致聚类分析方法，充分利用数据特征分布特点，自动识别聚类的数目，从而解决一致聚类中数目不能自动设定的问题。通过Minkowski距离优化调节一致矩阵参数，能够在不同的度量下获得有效的聚类结果，且由于算法本身机制集成了多种聚类算法，该法还具备一定的鲁棒性。仿真结果表明本文算法在聚类数目的确定精度和准确度上优于其他一致聚类算法。
当前铜矿泡沫浮选过程生产环境恶劣且长期依靠人工肉眼现场监测，受到工人主观经验影响，易导致浮选工况操作波动异常，引起浮选药剂等资源和能源的浪费。随着计算机技术、图像处理技术、智能控制等领域的迅速发展，机器视觉技术在矿物泡沫浮选领域得到越来越广泛的应用，为浮选生产过程提供丰富的实时监控信息。
通过视觉图像系统及液位、压力等工艺参数传感器测量，浮选生产现场积累了大量反映矿物生产状态的泡沫图像数据和生产操作信息，如何有效地分析和利用这些数据对浮选过程工况的分类、识别及过程调控具有重要意义。为此，本文提出了基于Minkowski距离的一致聚类分析方法，并应用到铜矿泡沫浮选过程工况的判别，取得了较好的聚类效果，有助于实现生产实时工况的自动判别。
1 一致聚类方法
常规聚类分析过程中，由于单一的聚类算法无法获得对所有数据的最优聚类结果，融合多种聚类算法的一致聚类方法引起研究人员的关注。一致聚类具体算法流程如图1所示。
利用聚类算法集成的一致聚类方法的出发点主要通过进行多次采样或结合多种聚类算法对数据进行分析，获得反映数据类别信息的一致矩阵，从而进行数据的划分。一致聚类算法已在基因数据分析及文本聚类分析等应用中取得了较好的效果。当前一致聚类主要有两类算法：基于重采样的一致聚类方法和基于迭代的一致聚类分析方法。
1.1 基于重采样的一致聚类方法
基于重采样的一致聚类算法输入样本数据为D={e1，e2，…，eN}，聚类方法采用谱聚类方法，一般把重采样分段采样比例设为80%，采样次数为H，聚类数目集合为K={k1，k2，…，kj}（j=length（K），即设定聚类数目序列长度），输出为聚类数目集合D，一致矩阵为M。基于重采样的一致聚类算法流程如下所示：
结合重采样或交叉验证等技术来模拟原始数据的扰动，该法是通过多次运行某一聚类算法（例如随机选取起始点的K-means或基于模型的贝叶斯聚类方法等）来获得类别稳定性，提供了一种可视化的途径来观察类别数目、类别成员以及类别边界等信息。
大量实验表明，尽管该方法适合基因表达数据的聚类，但对其他类别聚类效果不佳，其原因为：重采样随机采样大部分样本，采样次数以及采样比例对算法影响大；基于重采样的一致聚类分析方法中确定聚类数目的准则不统一，算法中△（k）为不同聚类数目下CDF曲线与横轴包围面积的变化量，其最大值对应最终的聚类数目，将△（k）变化值作为判断聚类数目的标准不确定。针对这些问题，一些学者提出了基于迭代的一致聚类方法。
1.2 基于迭代的一致聚类分析方法
该方法遵循一致聚类方法的基本思路，不同之处在于不需要对样本进行重采样，而是利用了多种聚类算法分别对同一样本数据进行聚类，获得一致矩阵，并通过将随机游走的策略引入一致矩阵的分析中，获得了概率转移矩阵，然后通过分析概率转移矩阵的特征值进而确定聚类的数目。如果矩阵特征值不能明显反映聚类信息，则将一致矩阵代替相似度矩阵进行多次迭代，最终获得能够反映聚类数目的特征值分布。该法采用多种聚类算法，克服了仅采用一种聚类算法的局限性，但仍存在缺陷，包括迭代的次数及迭代终止的条件不明确性，相似度矩阵的确定方法单一，仅依赖高斯距离公式进行标度等问题。
针对上述两类聚类方法存在的问题，本文通过分析这两类方法的特点，提出了基于Minkowski距离的一致聚类分析方法，有效地避免多次迭代，能较准确地获得聚类数目信息。
2 基于Minkowski距离的一致聚类算法（CCBM）
本文提出了一种基于Minkowski距离的一致聚类数目自动识别为核心算法的一致聚类方法（CCBM-consensusclusteringbasedMinkowskidis-tance）。该方法集成多种聚类算法，与以上两种一致聚类方法不同之处在于相似度矩阵的构建及聚类算法的选择上。为了克服重采样、迭代方法采样数目和迭代次数不能有效的最优确定等缺点，考虑到Minkowski距离公式能够准确刻画数据大范围的相似度量信息，本文方法采用Minkowski距离对输入数据进行了不同的度量，从而完成参数设定并对相似度矩阵进行一致聚类，并确定最能反映聚类信息的相似度度量，不需要迭代即能较准确获得聚类数目信息。下面详细说明本文所提出的方法算法流程，如图2所示。
2.1 Minkowski距离函数的设定
相对于常规的欧式距离或高斯距离，本文采用Minkowski距离公式，如式（1）-式（2）。其中，x和y为n维样本点，p和？为距离调整参数。当p取1时，式（1）为曼哈顿距离，刻画的是数据i与j横纵坐标差值的绝对值之和；当p取2时，式（1）为欧式距离，刻画的是数据i与。j的最短距离，即对角线距离；当p取无穷大时，式（1）为切比雪夫距离，刻画的是数据i与j在某维度上的最大差值；p也可取其他值（如p=0.5，0.1等小于1的数）。不同p值构建的Minkowski距离，利用算法分析会产生不同的聚类效果。式（2）中a为可调参数，通过调整p值及？值，该距离公式能够从不同角度反映数据（主要是声值影响）的相似度信息。
本文设定3种不同的p值（p分别取1，2，3）及5类不同？值（？分别取0.1，0.2，0.5，0.8，0.9），通过公式（1）-（2）获得不同相似度矩阵的构建（共15种），并对其进行聚类分析。由于以上构建的15种距离能够较全面地刻画数据间不同角度的相似信息，因此可以结合矩阵特征值分析方法，获得数据不同的特征值分布，为获得数据的聚类数目信息提供依据。
2.2 聚类算法的集成
聚类算法的集成需要考虑不同聚类算法的特点，选择合适的聚类算法对一致聚类算法的有效集成至关重要。谱聚类算法作为划分式聚类算法之一，能够在任意形状的样本空间上聚类，并且能收敛于全局最优解。而Newman贪婪算法作为复杂网络层次式分析方法，由于其收敛速度快等优点，在数据的聚类分析中有着广泛的应用。本文主要融合两种不同Laplacian矩阵构建的谱聚类算法（如式（3）-式（4））与复杂网络中的Newman贪婪算法的改进算法，一定程度上避免了聚类算法复杂度高的缺点。其中，D为将相似度矩阵每行之和赋值到对角线上的对角矩阵，L为相似度矩阵。
2.3 聚类数目的识别
2.3.1 聚类数目的识别准则
由于相似矩阵可看作一个无向图中节点之间的邻接矩阵，样本数可看作图中的节点数，相似矩阵中的权值可看作图中节点之间的边，并可以利用边的粗细代表权值的大小。
在建立的无向图中引入随机游走策略，获得转移概率矩阵P，P=D-1S，其中S为相似矩阵，D=diag（S·e），e是一个值全为1的向量。令σ（P）={1=λ1≥λ2≥…≥λn）作为P的谱分布，即特征值分布。经数学证明如果没有子类的划分，1=λ1≥λ2≥…≥λn中会有k个特征值[λ1，…，λk]接近于1，而特征值λk与λ2k+1之间的相对间距可以决定数据聚类的数目，这就为聚类数目的合理识别提供了数学依据。
2.3.2 一致相似矩阵及其特征值分布
首先确定所选择的聚类数目的序列，k=[k2，k2，…，kn]，其中n为所选择类别的数目，然后分别采用3.2节的三种聚类方法；根据聚类数目ki，i∈{1，2，…，n）进行分别聚类，共获得3×n个聚类结果，形成一致聚类矩阵M（如果第i个节点和第j个节点分到同一类，Mij为1，否则为0）构建；最后将一致相似矩阵M代替相似矩阵S，按照随机游走策略获得转移概率矩阵P，求得P的特征值分布，并通过特征值的分布获得聚类信息。
2.3.3 确定聚类数目的一致聚类算法流程
提出的基于Minkowski距离的一致聚类算法确定聚类数目的具体算法流程如图3所示。
具体步骤如下：
结合Minkowski距离函数（如式（1）-式（2））建立样本之间不同角度的距离测量，令声∈[1，2，3]，？∈[0.1，0.2，0.5，0.8，0.9]，以尽量覆盖参数的取值（共3×5=15种表示相似信息的情况）。
1）对于任取的一组p值和？值，令k=[k1，k2，…，kn]（依据所采用的数据规模，本文设k∈[8，9，10，11，12，13，14，15]，共8种聚类数目），对于每一k值，分别对距离刻画的相似信息采用上述3种聚类算法进行聚类，可得到3×8=24个聚类结果，由这24个聚类的结果构建一致相似矩阵Mi（i∈1，2，…，15]）。
2）重新对值p和？值进行取值，重复前一步，最后得到15个一致相似度矩阵M=[M1，M2，…，M15]，进而获得相应的转移概率矩阵P=[P1，P2，…，P1515]。
3）分别对转移概率矩阵Pi（i∈[1，2，…，15]）进行特征值分解，并根据特征值之间差值判别规则获得聚类的数目。
3 基于Minkowski距离的一致聚类算法（CCBM）分析
3.1 聚类数目识别分析
本文算法优越性体现在聚类数目的自动识别问题上，能够对数据进行分析并获得准确的聚类数目信息。为了验证算法有效性，测试数据为标准数据库中的UCI数据、图形数据及人工随机数据等代表性数据，如表1所示。
本文采用具有代表性的数据包括随机5类（仿真中利用Matlab软件mvnrnd函数设置均向量分别为[1，1]，[1，6]，[6，1]，[6，6]及[3.5，3.5]，对应方差均为0.1而获得的高斯数据）、Flame图形数据、Iris数据及Wine数据（对维数较高的采用SVD降维），仿真结果如图4-图7所示。
由图4-图7可以发现，本文算法对表1中数据聚类数目的识别非常准确，可有效地判断概率转移矩阵特征值分布（统计值接近于1的特征值数目）并确定聚类数目。
3.2 聚类数目结果分析
为了对比本文一致聚类方法与其他一致聚类算法的不同，针对表1的数据，分别进行聚类分析，得到的结果如表2所示。
由表2可发现，基于迭代的一致聚类算法耗时最少，主要是由于其迭代次数较少且没有重采样和参数选择环节，但是其判断数据类别数目不准确，如Iris数据的类别判断，其迭代终止的准则不明确，因此判断聚类数目不可靠。基于重采样的一致聚类算法耗时最多，主要是由于其迭代次数较大，这是为了提高精度而选择较多迭代次数的结果，但是其判断类别数目也不准确，如随机5类数据的类别判断。本文算法由于要对Minkowski距离公式参数进行选择，故耗时多于基于迭代的一致聚类算法，但是参数选择种类相对固定，耗时少于基于重采样的一致聚类算法。本文算法对于表1中4类数据聚类数目的判断准确，在聚类数目的识别准确性上优于其他两种一致聚类算法。
4 铜矿泡沫浮选的工况识别
在某企业铜矿泡沫浮选厂中铜优粗选流程如图8所示。铜矿石经过球磨粉碎过程，磨矿后的矿浆首先经过抑泥槽，后接搅拌槽，再通过粗选首槽（槽I）和粗选槽Ⅱ，其中矿物泡沫到精选过程，而矿浆到扫选过程。根据该流程生产工艺特点获知，对浮选生产有关键作用的是铜优浮选过程的粗选首槽。
在浮选过程人矿条件稳定的情况下，首槽泡沫会随着生产操作参数的改变发生变化。因此，根据浮选泡沫的表观形状和其带矿量的多少，可以将铜优浮选粗选首槽泡沫进行工况分类，并将分类结果对应相应的操作变量，以给出合理的操作建议，指导操作。如图9所示为浮选泡沫图像的3种不同浮选生产状态，铜矿泡沫形态的特征可以分别描述为：
A类泡沫：泡沫粒径、形状不规则，多为细长的扁形且以连生体存在，泡沫间的边缘不明显，矿化程度高，含泥多，泡沫负荷过多，泡沫颜色泛白、粘稠、稳定度高，但泡沫尺寸小、速度慢。
B类泡沫：泡沫颜色、大小适中、形状规则，气泡上有坚实的矿物负荷。
C类泡沫：泡沫上负荷量减少，泡沫多为虚泡、不稳定、易破裂或兼并。
通过现场观察和生产指标分析对比研究，在这3类浮选生产状态中，B类状态对应泡沫含矿最多。由于在铜优浮选粗选首槽已经构建由高分辨率工业摄像机、高频光源及高性能工业控制计算机等设备组成的泡沫图像采集平台，准确提取了反映生产工况的泡沫表征特征（包括纹理、大小、颜色等）。针对图9所示的3类泡沫图像特征，随机选取了实际生产过程的1个月200组数据，其中A，B，C类数据分别为50，100，50组数据，对其采用基于Minkowski距离的一致聚类算法分析，一致矩阵特征值分布如图10所示。由图可见，可以明显划分为3类工况，数据聚类的结果准确性高。原数据和聚类后的数据分别如图11和图12所示。
通过对比分析发现选取200组数据中只有2个误分点，正确率达到98.5%。因此，本文所提算法可用于实际铜矿泡沫浮选过程图像数据的有效聚类，从而有助于进一步实现浮选生产工况的自动识别，识别浮选泡沫生产状态，为浮选生产操作提供指导。
5 结论
基于大型数据集的聚类算法研究 篇5
针对大型的数据来说, 过去的聚类[1]手段存在下面两个关键的不足。首先就是其数据集不够稳定, 与低维相比, 高维的分布更加广泛, 这往往会出现数据之间等距的现象, 通常而言, 我们会按照距离来展开聚类工作, 这样意味着高维数据集的构建难度进一步加大[2];其次, 就高维数据集而言, 其内在的属性往往没有直接的联系, 所以基本上在所有维中存在类的概率为0[3]。
1 部分优先聚类算法 (Partial Priority Algorithm PPA)
就引言中的问题展开研究, 进而提出部分优先算法, 首先将第一类从原始数据中分离出来, 删除第一类数据后, 再分离形成第二类, 反复循环下去, 我们会发现其计算速度非常快, 但是不满足使用的准确度要求, 这种算法十分适用于准确度要求不是十分严格的数据集的计算。针对其准确度不足的情况, 我们结合使用了加权的方法来确定类中心, 以此来提升其稳定性与典型程度, 这对于聚类的稳定性、延伸性以及时效性都是十分有利的。
1.1 概念定义
1. r -邻域:其中心是某一个数据点, 半径用小写字母r表示。
2.典型样本p :其定义就是如果样本集A内部数据的r -邻域里存在有最基本的Minpts (密度阀值) [3]个数据, 那么该样本就叫做典型样本。
3.典型点C[4]:p中全部数据的平均值为典型点,
其中p中样本的数量用表示。
4.类中心[4]:即样本中全部数值的平均值。
1.2部分优先算法的设计案例
1.选择某一个数据集, 然后随机抽取其中的一个样本A , 确定A典型与否。任取样本中的某一个初始值, 设置好固定的r与Minpts。然后以该点作为圆心, 若Minpts的数值比r -邻域内的数据量小, 那么就可以确定样本A具有代表性;
2.如果A具有很好的代表性, 即确定其典型性, 那么我们可以利用公式 (1) 求解出C1, 其中C1是样本的典型点, 也就是样本的中心;
3.如果A不具有代表性, 即不具典型性质, 那么可以重新进行第一个环节, 一直到发现典型样本为止;
4.样本的中心聚类用C1表示, 利用公式
求解出C1 与样本A中各对象的间距;
5.假如C1与指定对象xi两者的间距没有大于或等于r , 那么我们将此对象合并进A内, 反之, 获取C1和其他对象xi+1两两之间的间距, 完成A内包含的全部对象。
该算法的流程图见图1:
1.3 PPA的优势
1.旨在有效加强典型范例和相应的典型点的计算速度, 此算法放弃选取数据集全部内容而是借助于随机挑选的方式从而获得典型样本, 与此同时典型点的分析过程仅出现1 次。
2.旨在增强典型点的代表水平, 增加r -邻域中的数据密度, 此计算方法制定典型样本数值的平均数为典型点, 另一方面此点也能够被当作聚类中心。
3.旨在下调旧有数据集的繁琐程度, 此算法在完成1 个类之后, 会把此类的数值从旧有合集内删除以避免重复。
面对数值的排列PPA并不具备敏感性, 这就会使PPA面向球形以及凸形集合时的分析速度更快。与此同时, PPA在样本平均数值处获得典型样本, 所以在处理异常数据情况上相对更为敏感, 评估异常点相对更为准确。PPA于聚类环节精简了旧有的合集, 大幅度下调了旧有合集的繁琐性, 因此我们不难发现其于功效上具备较大优势。PPA的分析能力、输入数据的敏感程度、面向异常数据的敏感程度、察觉聚类形状等方面和K-means clustering algorithm、DBSCAN clustering algorithm、COBWEB clustering algorithm、FCM clustering algorithm、单连接聚类算法、CLIQUE clustering algorithm、CUBE clustering algorithm等模型开展比对[5,6], 得出的相关结论详情见表1。
2 面向大型数据集的PPA的聚类融合
2.1 聚类融合基本思想
聚类融合 (clustering ensemble, CE) 旨在于消除单词聚类 (word clustering) 的较大波动性, 把合集映射为数据点的相似度随之求出融合的划分, 面向合集的归类途径为借助于1 种算法中的多项参数或是多项算法, 聚类成员的产生详情见图2。
CE的核心理念: 假定存在n项数据点X={x1, x2, ⋅⋅⋅, xn}, 面向X开展H次聚类求出H项聚类, π={π1, π2, ⋅⋅⋅, πH}, 在此之中πk (k=1, 2, ⋅⋅⋅, H) 是第k次求解数据。假定存在共识函数 r, 详情见图3。
共识函数 (consensus function, CF, 也称为一致性函数) [7]的定义标准为只要可以将需要聚类的所有聚类成员借助于其一标准完成融合过程, 以共协矩阵[8] (Co-association matrix) 为例, 相应的功能为评价数据内部的关联性, 函数方程详见 (3) :
接下来我们面向前面获得的H项结果展开融合, 求出所需的聚类结果π'。聚类融合的详情情况见图4。
2.2聚类融合算法的设计
我们假设一数据合集X={x1, x2, ⋅⋅⋅xn},
, 借助于PPA算法把它进行归纳, PPA算法的特征[9]为所有划分行为均会先出现第1个类, 随后采取融合的途径得到所需的第1个类。第1次归纳总结一直到第r次归纳总结的第1个类为, 相关的类中心则是, 旨在确保所有划分行为出现的第1个类存在差异, 算法设计借助于改变数据的输入顺序从而达到目的。
融合方式[10,11]定义为:借助于加权的方法从而求出第1 类的类中心, 此类中心的权重需要借助于此类中的全部数据量和每类数据量之和的比例而获得。
为类CiC所含的数据量, 1V定义成所需的第1个类的类中心。随着1V的求出, 再确定空集1T, 将1V赋予1T作为类中心开始聚类, 假设存在阀值r, 利用PPA算法的第5环节, 求出的1T即是所需出现的第1个类。于所有划分行为中把1T包括的数值剔除, 从而有效下调数据的繁琐性。
按照上述步骤获得剩余的k-1 个类。 由于Vi (i=1, 2, ⋅⋅⋅, k) 存在的典型性, 所以出现T1, T2, ⋅⋅⋅, Tk之后, 余在旧有合集内的数据接近于0, 算法设计将余下数值平分成k份, 再依次移到T1, T2, ⋅⋅⋅, Tk中, 函数 (5) 即是所有类中心的算法函数, 各类产生的详情见图5。
其中, Vi (i=1, 2, ⋅⋅⋅, k) 为各个类的类中心。
2.3 聚类融合算法的优势
1.旨在让类中心的代表水平以及相应的典型程度更为突出, 分析归类更为精确, 类中心借助于加权的方法从而实现此目的, 借助于公式 (5) 获得所有类中心。
2.旨在增加计算性能, 采用的类中心让原有数据集的内容极限精简。
3.旨在下调数据集的复杂程度, 于归类期间把已完成分类的部分从原有数据集内剔除。
3 算法测试结果分析
采取9组从UCI Machine Learning Repository合集中获得的数据 (Size<2*104) , 各为Fertility, Car Evaluation, Abalon, Artificial Characters, ISOLET, Cal It2 Building People Counts (CBPC) , Gas Sensor Array Drift Dataset (GSADD) , p53 Mutants, Letter Recognition详细参数见表2, 为验证算法是否具有稳定性, 同时测试其可行性, 面向表2 囊括的9 组合集分别开展5 次PPA以及基于PPA的聚类融合算法, 求解获得平均时间值、精度值和方差值。
按照表3 以及图6 中的内容, 我们不难发现PPA算法和基于PPA的聚类融合 (EPPA) 算法相比较, PPA的运算效率更高一些, 然而于精度层面开展比较, 则是EPPA更胜一筹。按照获得的实验结果中的方差开展对比, 我们发现PPA的鲁棒性更胜一筹。按照表4 以及图7 中的内容, 我们能够得出结论:EPPA于处理大型数据过程中的抗外界干扰能力和其可靠性均具有显著强势。
根据获得的实验结果我们发现PPA以及EPPA容易受处理的数据量的多少以及维数大小的作用, 于17, 000 数据处出现转折情况, 与此之前要更平稳, 之后就出现时间增加过快的现象。于精度层次上考虑, 数据集超过6, 000 的情况下EPPA开始稳定, 能够得出结论:EPPA的稳定性和可靠程度较高, 面向未知数据集的计算上存在着巨大的潜力。
4 结论
本研究将常见的聚类算法开展一定程度上的优化, 得到部分优先聚类算法, 增强了算法的处理能力, 提高其效率, 然而于精度层次上考量, 其可靠性仍然有待于后续优化, 本研究于部分优先聚类算法的基础上开展了聚类融合, 避免了此算法缺乏精度的缺点, 增强其算法精度, 使其于可扩展程度、鲁棒性、可靠程度等方面均有着传统聚类算法无法匹敌的优势, 对于大型数据集的计算具有举足轻重的作用。
参考文献
[1]郑文超, 徐鹏.利用word2vec对中文词进行聚类的研究[J].软件, 2013 (12) :160-162.
[2]翁芳菲.聚类融合算法研究及其应用[D].厦门:厦门大学, 2008.
[3]侯娟.聚类融合算法及其应用研究[D].长沙:中南大学, 2010.
[4]侯德森.一种面向大数据集的部分优先聚类算法[D].保定:华北电力大学, 2010.
[5]申超波, 王志海, 孙艳歌.基于标签聚类的多标签分类算法[J].软件, 2014, 35 (8) :16-21.
[6]黄少滨, 李建, 刘刚.一种基于自适应最近邻的聚类融合方法[J].计算机工程与应用, 2012, 48 (19) :157-162.
[7]刘丽敏, 樊晓平, 廖志芳.选择性聚类融合新方法研究[J].计算机应用研究, 2012, 29 (11) :4031-4034.
[8]李建.聚类融合研究及其应用[D].哈尔滨:哈尔滨工程大学硕士学位论文, 2010.
[9]陈磊磊.不同距离测度的K-Means文本聚类研究[J].软件, 2015, 36 (1) :56-61.
数据挖掘中聚类算法的研究 篇6
1 传统聚类方法及其研究进展
1.1 划分法
给定一个包含n个数据对象的数据集，划分法构建数据的k个划分，每个划分表示一个类，并且k≤n。同时满足如下的要求： (1) 每个组至少包含一个对象; (2) 每个对象属于且仅属于一个组。给定要构建的划分的数目k，创建一个初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。判定一个好的划分的一般准则是：在同一个类中的对象之间尽可能“接近”或相关，在不同类中的对象之间尽可能“远离”或不同，即使下列准则函数最小：
式中的E是数据集中所有对象的平方误差的总和;mi是类Ci的平均值(或中心点)，p是数据空间中的数据对象(p和mi都是多维的) 。为了达到全局最优，基于划分的聚类要求穷举所有可能的划分。基于划分的方法 (Partitioning Method) ，其代表算法有K-MEANS、K_MEDOIDS、CLARANS等。
1.2 层次法
层次法对给定的数据对象集合进行层次似的分解。按层次分解的形成方式，层次法可分为凝聚和分裂两大类。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个类，然后相继地合并相近的类，直到所有的类合并为一个(层次的最上层)，或者达到一个终止条件为止。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个类中。在迭代的每一步中，类被分裂为更小的类，直到每个类只包含一个对象，或者达到一个终止条件为止。在凝聚或者分裂层次聚类方法中，通常以用户定义的希望得到的类的数目作为结束条件。在类的合并或分裂过程中，需要考察类间的距离。类间距离的度量广泛采用如下四种方法：
最小距离：dmin (Ci, Cj)=minp∈Ci, p'∈Cj|p-p'|
最大距离：dmax (Ci, Cj)=maxp∈Ci, p'∈Cj|p-p'|
平均值距离：dmcan (Ci, Cj)=|mi-mj|
平均距离：
层次方法 (Hierarchical Method) ，其代表算法有BIRCH、CURE、CACTUS等。
1.3 基于密度的方法
绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状的类，而在发现任意形状的类上有困难。因此，出现了基于密度的聚类方法，其主要思想是：只要邻近区域的密度(对象或数据点的数目)超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域内必须至少包含某个数目的点。这样的方法可以过滤“噪声”数据，发现任意形状的类。但算法计算复杂度高，一般为O (n2) ，对于密度分布不均的数据集，往往得不到满意的聚类结果。其代表算法有DBSCAN和OPTICS等。
1.4 基于网格的方法
基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构(即量化空间)上进行。这种方法的主要优点是它的处理速度很快，其处理速度独立于数据对象的数目，只与量化空间中每一维的单元数目有关。但这种算法效率的提高是以聚类结果的精确性为代价的。它的代表算法有STING、CLIQUE、WAVE-CLUSTER等。
1.5 基于模型的方法
基于模型的方法为每个类假定一个模型，寻找数据对给定模型的最佳拟合。基于模型的方法分为两类：统计学方法和神经网络方法。
2 聚类方法的最新发展
2.1 基于模糊的聚类方法
在实践中，大多数对象没有严格的属性，它们的类属和形态存在着中介性，适合软划分。由于模糊聚类分析具有描述样本类属中间性的优点，能客观地反映现实，逐渐成为当今聚类分析研究的主流。最早也最系统地表达和研究模糊聚类问题的著名学者Ruspini，率先提出了模糊划分的概念。基于这一概念，人们相继提出了多种模糊聚类分析方法，比较典型的有基于相似性关系和模糊关系的方法、基于模糊等价关系的传递闭包方法、基于模糊凸轮的最大树方法以及基于数据集的凸分解、动态规划和难以辨识关系等方法。然而上述方法均不适于大数据，难以满足实时性较高的场合需要。其中，基于目标函数的模糊聚类方法把聚类归结成一个带约束的非线性规划，通过优化求解，获得数据集的模糊划分和聚类，成为新的研究热点。
2.2 基于粒度的聚类方法
从表面上看，聚类和分类有很大差异———聚类是无导师的学习，而分类是有导师的学习。具体说来，聚类的目的是发现样本点之间最本质的抱团性质的一种客观反映;分类需要一个训练样本集，由领域专家指明，而分类的这种先验知识却常常是主观的。如果从信息粒度的角度来看，就会发现聚类和分类的相通之处:聚类操作实际上是在一个统一粒度下进行计算的;分类操作是在不同粒度下进行计算的。在粒度原理下，聚类和分类的相通使得很多分类的方法也可以用在聚类方法中。作为一个新的研究方向，虽然目前粒度计算还不成熟，尤其是对粒度计算语义的研究还相当少，但是相信随着粒度计算理论本身的不断完善和发展，在今后几年，它必将在数据挖掘中的聚类算法及其相关领域得到广泛应用。
2.3 量子聚类
在现有的聚类算法中，聚类数目一般需要事先指定，如Kohenon自组织算法、K2means算法和模糊K2means聚类算法。然而，在很多情况下类别数是不可知的，而且绝大多数聚类算法的结果都依赖于初值，即使类别数目保持不变，聚类的结果也可能相差很大。受物理学中量子机理和特性启发，可以用量子理论解决此类问题。一个很好的例子就是基于相关点的Pott自旋和统计机理提出的量子聚类模型。它把聚类问题看做一个物理系统。并且许多算例表明，对于传统聚类算法无能为力的几种聚类问题，该算法都得到了比较满意的结果。
2.4 核聚类算法
目前比较流行的聚类算法，如K2means、模糊K2means聚类算法和Kohonen自组织神经网络等，只对一些经典分布的样本奏效。这些方法的有效性在很大程度上取决于样本的分布情况。若一类样本散布较大，而另一类散布较小，这些方法的聚类效果就比较差。
核聚类方法增加了对样本特征的优化过程，利用Mercer核把输入空间的样本映射到高维特征空间，并在特征空间中进行聚类。核聚类方法是普适的，并在性能上优于经典的聚类算法，它通过非线性映射能够较好地分辨、提取并放大有用的特征，从而实现更为准确的聚类;同时，算法的收敛速度也较快。在经典聚类算法失效的情况下，核聚类算法仍能够得到正确的聚类。
2.5 谱聚法
最近一类有效的聚类方法开始受到广泛关注。该类方法建立在谱图理论基础之上，并利用数据的相似矩阵的特征向量进行聚类，统称为谱聚类方法。谱聚类算法是一种基于两点间相似关系的方法，适用于非测度空间。算法与数据点的维数无关，而仅与数据点的个数有关，由此可避免由特征向量的过高维数所造成的奇异性问题。谱聚类算法是一个判别式算法，不用对数据的全局结构作假设，而是首先收集局部信息来表示两点属于同一类的可能性;然后根据某一聚类判据作全局决策，将所有数据点划分到不同的数据集合中。通常这样的判据可以在一个嵌入空间中得到解释，该嵌入空间是由数据矩阵的某几个特征向量张成的。谱方法成功的原因在于:通过特征分解，可以获得聚类判据在放松了的连续域中的全局最优解。
与其他方法相比，谱聚类方法具有明显的优势。该方法不仅思想简单、易于实现、不易陷入局部最优解，而且具有识别非凸分布的聚类能力，适合于许多实际应用问题。目前，谱聚类方法已应用于语音识别、视频分割、图像分割、VLSI设计、网页划分、文本挖掘等领域。尽管如此，谱聚类方法目前仍处在发展初期，算法本身仍存在许多值得深入研究的问题。
3 结束语
在实际应用中，应根据具体问题具体分析，选择最佳的聚类方法。纵观数据挖掘中聚类分析方法的发展，可以看出聚类分析的新趋势： (1) 新方法不断涌现; (2) 传统聚类方法的融合发展，如基于密度、网格和距离的聚类新方法CUBN; (3) 为了提高分类的性能，根据实际问题的需要，有针对性地综合了众多领域的技术机器学。如机器学习、数据挖掘、模式识别、物理等。相信随着这些领域中相关理论的发展、完善和相互渗透，聚类方法也将得到更进一步的发展。
参考文献
[1]王实, 高文.数据挖掘中的聚类方法[J].计算机科学, 2000 (4) .
[2]行小帅, 焦李成.数据挖掘的聚类方法[J].电路与系统学报, 2003 (1) .
数据挖掘中聚类算法研究综述 篇7
聚类分析是将物理或抽象的集合分割为由类似对象组成的多个类的过程, 使得位于同一类中的对象有高度的相似性, 而不同类之间对象差别较大[1]。聚类与分类不同, 在分类模型中, 存在样本数据, 这些数据的类标号是已知的, 分类的目的是从训练样本集中提取出分类的规则, 用于对其它类标号未知的对象进行类标识。在聚类中, 预先不知道目标数据的有关类的信息, 需要以某种度量为标准将所有的数据对象划分到各个簇中。因此, 聚类分析有时又称为无指导的学习或观察式学习。
在过去的几十年中, 许多优秀的聚类算法已经被开发出来, 具体可以分为划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法等。
1 划分方法 (partitioningmethod)
给定一个有N个元组或者记录的数据集, 划分方法将构造K个分组, 每一个分组就代表一个聚类, 其中K≤N。而且这K个分组满足下列条件: (1) 每一个分组至少包含一个数据记录; (2) 每一个数据记录属于且仅属于一个分组 (注意:这个要求在某些模糊聚类算法中可以放宽) ;对于给定的K, 算法首先给出一个初始的分组方法, 以后通过反复迭代的方法改变分组, 使得每一次改进之后的分组方案都较前一次好, 而所谓好的标准就是:同一分组中的记录越近越好, 而不同分组中的记录越远越好。使用这个基本思想的算法有:K-MEANS算法[2]、K-MEDOIDS[3]算法等。
1.1 K-MEANS算法 (K-平均算法)
K-平均算法是一种重要的聚类算法, 它是目前应用最广的基于划分的聚类算法之一, K-平均算法以K为参数, 把N个对象分为K个簇, 使簇内具有较高的相似度, 而簇间的相似度较低。
K-MEANS算法的处理步骤为:
步骤一:随机选取k个点作为初始簇中心;
步骤二:重复;
步骤三:根据当前簇中心 (平均值) , 将其余对象赋给距离最近的中心点所代表的簇;
步骤四:重新计算每个簇的平均值;
步骤五:直到划分不发生变化。
优点:K_平均算法实现起来比较简单其计算复杂度为 (nkt) , 其中n为对象个数, k为聚类个数, t为循环次数, 它具有可扩展性。
缺点:K_平均算法有以下四个缺点:
(1) K-平均算法只适用于簇中对象的均值有意义的情况。
(2) 用户必须事先指定聚类个数K。
(3) K-平均算法还不适合发现非凸状的聚类。
(4) K-平均算法对噪声和异常数据非常敏感。因为这类数据可能会影响到簇中对象的均值。
1.2 K-MEDOIDS算法 (K-中心点算法)
K-中心点算法不采用簇中对象的平均值作为参照点, 而是选用簇中位置最中心的点 (中心点) 作为聚类的中心点。剩余的对象根据其与代表点的距离分配给最近的一个簇。然后反复地寻找更好的质心, 以改进聚类的质量, 直到不再发生变化为止。
K-中心点聚类算法虽然比K-平均算法更健壮, 但K-中心点聚类算法的执行代价要比K-平均算法高得多。
2 层次方法 (hierarchicalmethod)
层次方法对给定的数据集进行层次似的分解, 直到某种条件满足为止, 具体又可分为“自底向上” (凝聚层次聚类方法) 和“自顶向下” (分裂层次聚类算法) 两种方案。在“自底向上”方案中, 初始时每一个数据记录都组成一个单独的组, 在接下来的迭代中, 它把那些相互邻近的组合并成一个组, 直到所有的记录组成一个分组或者某个条件满足为止。代表算法:CURE[4]。
CURE算法是一种很新颖的层次聚集算法, 采用了基于质心和基于代表对象方法之间的中间策略, 它选择数据空间中固定数目的具有代表性的点来代表一个簇, 并将这些点乘以一个适当的收缩因子, 使它们更靠近簇的中心。它的时间复杂度在最坏情况下为n2logn。优点是选择多个代表使得该算法可以适应非球状的几何形状, 簇的收缩或凝聚可以有助于控制噪声的影响, 同时该方法采用了随机抽样与分割相结合来提高效率, 对大型数据库有良好的收缩性。
3 基于密度的方法 (de n s it y-based method)
基于密度的方法与其它方法的一个根本区别是:它不是基于各种各样的距离的, 而是基于密度的, 这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。这种方法的基本思想是:只要一个区域中的点的密度大过某个阈值, 就把它加到与之相近的聚类中去。代表算法有:DBSCAN[5]等。
DBSCAN (Density Based Spatial Clustering of Applications with Noise) 的算法思想是:检查一个对象的ε领域的密度是否足够高, 即一定距离ε内数据点的个数是否超过Minpts来确定是否建立一个以该对象为核心对象的新簇, 再合并密度可达簇。它可以在带有“噪声”的空间数据库中发现任意形状的聚类, 另外此算法可以通过不断执行区域查询来实现聚类。其缺点是对输入参数ε和Minpts相对敏感, 且这两参数难以确定。在算法复杂度上, 若采用空间索引, 其时间复杂度为O (n·logn) , 否则仍为O (n2) 。
4 基于网格的方法 (grid-basedmethod)
基于网格的方法首先将数据空间划分成为有限个单元 (cell) 的网格结构, 所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快, 通常这是与目标数据库中记录的个数无关的, 它只与把数据空间分为多少个单元有关。代表算法有:STING。
STING算法 (Statistical Information Grid) 的基本思想是:先将数据空间划分成矩形单元, 对应不同级别的分辨率, 存在着不同级别的矩形单元, 这些单元形成一个层次结构:高层的每个单元被划分为多个低一层的单元。高层单元的统计信息可以由计算低层单元获得, 而统计信息的查询则采用自顶向下的基于网格的方法。这种方法的主要优点是:网格结构有利于并行处理和增量更新, 且其计算是独立于查询的, 另外它的处理效率很高, 它通过扫描数据库一次来计算单元的统计信息, 因此其聚类时间复杂度为O (n) , 在层次结构建立后, 其查询处理的时间复杂度为O (m) , 其中, m为最低层网格单元的数目。它的缺点是聚类质量取决于网格结构最低层的粒度, 而粒度的大小会明显地影响处理代价;另外, 它所有的聚类边界或者是水平的, 或者是竖直的, 没有对角的边界。
5 基于模型的方法 (m o d e l-based method)
基于模型的方法给每一个聚类假定一个模型, 然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定是:目标数据集是由一系列的概率分布所决定的。通常有两种尝试方向:基于统计的方法和基于神经网络的方法。
神经网络用于聚集的方法是将每一个聚类看作一个标本, 它是这个类的“典型”, 但不需和某个具体的记录或例子相对应。通过基于某种距离的计算机方法, 找到与标本最相似的对象, 并把它分到这个类别。神经网络方法, 是利用神经网络模型对采样样本进行学习, 并进行聚类的算法。它以神经计算为理论基础, 并与人工神经网络的数学模型以及人脑的神经网络研究有着紧密联系。所以, 是一个富有挑战性的研究领域。神经网络聚类有两个比较典型的方法:竞争学习和自组织特征映射。
6 其他聚类算法
近年来出现了一些针对特殊数据类型和带有约束条件的特殊问题的聚类算法, 如文本聚类[6,7]、带约束的聚类[8]等等, 还出现了将多种聚类技术结合起来的新的聚类算法[9,10,11]12]。
7 小结
聚类分析是数据挖掘领域研究的重要分支, 聚类分析广泛应用于许多领域, 本文列举了聚类分析的一些很有价值的方法。但是, 大量的理论问题尚未解决, 聚类分析的效率等理论问题值得深入研究。
摘要：聚类分析是数据挖掘领域一个活跃的研究分支, 在数据挖掘中已经开发出许多聚类算法, 具体可分为划分方法、层次方法、基于密度方法、基于网格的方法、基于模型的方法。本文对上述几类聚类分析算法进行了讨论, 对每种聚类算法都举出了典型例子, 并作了分析, 指出了各种算法的优缺点并对聚类技术未来的发展作出了展望。
高维空间数据库聚类算法研究 篇8
聚类分析是数据挖掘的重点研究领域,也是研究的热点之一,当前各种聚类技术层出不穷。随着聚类技术的发展以及工程实践应用的深入,聚类的研究目标渐渐地针对的是大型、高维的空间数据库,这给聚类带来了挑战。实际上,在人们日常生活所接触和利用的现实数据中,大约有80%的数据与地理位置、属性及其空间分布有关[1]。
1 空间数据库聚类的基本概念
空间数据聚类是空间数据挖掘的一个重要分支,它是根据某个相似性准则对空间实体集进行自动分组或类,使空间数据库中的数据达到组内差异最小、组间差异最大的过程[2]。空间数据库聚类就是将空间数据库分成相似的对象集。设X是数据集,即:X=(x1,x2……,xm),将X分割成n个类(簇)C1……,Cn,使其满足下面三个条件:Ci≠,i=1,2...n;C1∪C2∪…∪Cn=X;Ci∩Cj≠;i≠j;i,j=1,2...n;其中聚类Ci中包含的对象彼此“更相似”,与其他类中的对象“不相似”[3,4]。
2 主要的空间数据库聚类算法
目前已经研究出来的空间聚类算法有很多种,采用不同的聚类算法,可能有不同的聚类结果。算法的选择主要取决于具体的数据集、数据类型、聚类的目的以及应用背景。对于高维空间数据库,从数据挖掘的技术角度来看,主要的高维空间数据库聚类算法分为层次方法,划分方法,基于密度的方法,基于网格的方法和基于模型的方法[5]。
2.1 层次方法
层次方法(hierarchical method)(也称系统聚类法,系统聚类法为传统统计学方法)采用距离作为衡量聚类的标准,根据层次分解有“自底向上”和“自顶向下”两种方式,进一步划分为合并的和分裂的两种方法。其中合并层次聚类初始时将每一个对象作为单独的簇,然后合并这些簇成越来越大的簇,直到满足某个条件为止或者所有对象在一个簇中。而分裂层次聚类则是先将所有对象看成在一个簇中,然后把它逐渐细分成越来越小的簇,直到满足某个条件为止或每个对象自成一簇。层次聚类法简单直接并且易于理解和应用,但缺点在于:一旦合并或者分裂执行,则不能修正,也没有办法更正错误;没有良好的伸缩性,时间复杂度是O(n2),为克服这一缺点,有人将层次聚类和迭代重定位等聚类技术进行集成,形成多阶段聚类。代表算法有:BIRCH算法[6],CURE算法[7],CHAMELEON算法[8]。
2.2 划分方法
划分方法也叫分割方法,是将一个包含有n个数据对象的数据库组织成k(k≤n)个划分,其中每个划分表示一个类或簇,而且这k个划分满足2个要求:(1)每一个划分至少包含一个对象;(2)每一个对象属于且仅属于一个划分,图1描述了划分方法的基本框图。
对于事先给定的K,算法首先创建一个初始划分,然后采用反复迭代的方法改变划分,使得每一次迭代之后的分组方案都比前一次好。而好的划分标准就是:同一分组中的对象越“接近”越好,而不同分组中的记录越“远离”越好。最著名的两种划分方法是基于质心的k-means方法[9]和基于粒计算的K-medoids算法。
2.3 基于密度的方法
基于密度的方法与层次方法、划分方法的根本区别是:它不是采用距离来衡量相似性的,而是基于密度的。该方法的核心思想就是:只要在指定空间区域中的点的密度大于某个设定的阈值就把它加到与之相近的聚类中去。其优点是可以发现任意形状的簇,抗干扰能力强,较适合空间数据聚类。代表算法有DBSCAN算法、OPTICS算法、DENCLUE算法[10]、SUBCLUSTER算法等。DBSCAN算法通过不断扩大足够高密度区域来进行聚类,它能处理噪声及发现空间数据库中任意形状的聚类,聚类速度快;此算法将一个聚类定义为一组“密度连接”的点集[11]。OP-TICS算法是为聚类分析生成一个增广的簇排序,并不显性地产生结果类簇,这个排序表示了各样本点基于密度的聚类结构[12]。
2.4 基于网格的方法
基于网格的方法首先把数据空间划分成为一定数目单元的网格结构,所有的聚类操作都是以网格中的单元对象进行的。这样处理的主要优点是处理速度很快,处理时间与目标数据库中记录的个数是无关的,只与把数据空间分为多少个单元有关。缺点是划分网格单元太粗糙时,不同聚类对象会被划分到一起,划分网格单元太细化时,会得到很多小的聚类,所以,基于网格的聚类算法存在如何选择合适的单元大小和数目的问题。另外,此算法不适合处理高维的数据,因为网格单元的数目随着维数的增加而呈指数级增长。代表算法有STING算法[13]、CLIQUE算法[14],WAVE-CLUSTER算法[15]则是基于网格与基于密度相结合的方法。
2.5 基于模型的算法
基于模型的方法给每一个簇假定一个模型,接着去寻找数据对给定模型的最佳拟合。它通过构建反映数据点空间分布的密度函数来定位簇,同时还需要考虑噪声数据和离群点的影响,从而产生比较鲁棒的聚类方法。它的一个潜在的假设是,目标数据集是由一系列的概率分布所决定的,代表算法有:统计方法COBWEB、EM、神经网络等。
3 空间数据库聚类方法比较
理想的空间聚类算法应该具有可扩展性、能发现空间任意形状的聚类、用户输入参数少、对噪声不敏感、能处理高维数据、可解释性和可用性。针对这几方面,对以上几种聚类算法进行了比较,见表1。
4 基于高维空间的聚类算法的改进
DBSCAN是一个典型的基于密度的空间聚类算法。其基本思想是采用一定半径范围内包含的空间对象实体的最小数目来定义空间密度的概念,只要一个区域中实体对象的密度大于某个阈值,就将该数据点加入到与之相近的聚类中去。
DBSCAN从任一对象p开始,根据参数ε和Min Pts提取所有从p直接密度可达的对象,如果p是核心对象,那么从p所有密度可达的对象标记为同一类(簇),并从他们进一步扩展,直至找到一个完整的聚类。如果p不是核心对象,则p标记为噪声,然后再选择一个新的对象进行扩展,得到下一个聚类,直到所有的对象都被标记为止,这个过程可能会合并一些密度可达的簇。当没有新的点可以被添加到任何簇时,算法结束。
DBSCAN的算法描述如下:
输入:ε为邻域半径、min Pts是一个簇中点的最小实体数量、SDB数据集
输出:达到阈值要求(ε和min Pts)的聚类区域。
从SDB中读取一个未被处理过的点;
do{
if(该点是核心对象)
寻找所有从该点密度可达的对象,标记为一个簇;
else
读取的点是非核心对象,不做处理;
读SDB的下一个空间对象;
}while(所有点都被处理过);
未加入任何簇的点标记为孤立点(噪声)。
该算法有两个明显的缺点:当数据量增大时,要有较大的内存支持,I/O开销也大;当空间聚类的密度不均时,聚类间距离大,聚类质量较差。针对这两点不足,下面给出改进后的算法,该算法采用分区的并行方式对其进行改进。先将高维空间内数据库降维为二维,再对二维数据库进行分区,分区后对每个区的数据进行聚类,然后再将聚类后的数据合并。
改进后的聚类算法如下:
输入:ε为邻域半径、min Pts是一个簇中点的最小实体数量、SDB分区后的数据集
输出:达到阈值要求(ε和min Pts)的聚类区域。
算法检索完一个点的邻域后,随机选取另一个未被分类的点,重复以上过程,直至所有的点都被分类或归为“噪声”。算法中,考察q的ε-邻域内的点,是最耗时的部分,在没有空间索引的情况下,时间复杂度为O(n2),如果采用空间索引,时间复杂度约为O(1ogn)。
5 总结及研究展望
目前,空间数据挖掘及其相关问题还是一个崭新的研究课题,有关的研究才刚刚开始还不是很深入,需要研究的问题还很多,如医疗成像,卫星探测,遥感解释,多媒体数据库等众多带有价值信息的空间数据的出现,使得空间数据的挖掘成为一个重要领域。由于空间数据库的规模巨大,数据类型和存取方法复杂,所以探索高效的空间数据挖掘一直是一个富有挑战的难题。本文主要是对空间数据的聚类技术进行研究和比较,并改进了基于高度的DB-SCAN算法,该算法减少了I/O开销,在对空间多维数据经过降维、分区后再进行聚类,提高了算法的效率,使其更适合高维空间数据库的数据聚类。
数据流聚类算法研究 篇9
为了解决大规模数据计算、完成分布在不同地理位置的数据集成、局域网与广域网的无缝结合、环境监测传感器数据聚类等应用, 分布式数据流挖掘技术[1]已经成为数据挖掘技术的研究的主要内容, 数据流聚类作为流数据挖掘的一个重要分支, 其研究将进一步促进知识发现, 发现事物的变化趋势。
目前分布式结构主要呈“三角形”或“倒立树”结构, 而这种结构也是分布式数据流聚类的主要框架结构。数据流聚类研究的主要目标是将数据流划分为若干个有意义的类, 根据生成的类来预测事物变化趋势。由于数据流的迅速变化性、流动性和持续性, 产生数据流的底层模型可能会发生变化, 这种随时间或者连接结构变化的数据流, 我们将其称为进化的数据流。
为了找到不断变化数据聚类有效的算法, Clu Stream[2,3]提供了一个解决数据流中聚类问题的框架, 虽然该框架十分优秀, 但是还是有需要改进的地方。它使用一个在线的微簇过程对数据流进行初步聚类, 使用另一个离线的微簇过程对聚类结果再次分析, 将数据流看成是一个随着时间推移而不断变化的过程, 由于Clu Stream基于K-means聚类, 对球形的聚类有较好的聚类结果, 对于除了球形的其他形状的聚类, 聚类效果仍不令人满意。
本文提出一种分布式密度和中心点的数据流聚类算法DDCS-Clustering算法, 构建了分布式环境, 实验结果表明, 该算法具有较高的数据流聚类质量, 并且有效降低系统的通信代价。
1基本概念
由于实际数据流应用中大多为进化的数据流, 即随着时间的推移, 其聚类模型可能发生改变, 生成的簇不可预测, 最近元组所蕴含的知识往往比历史元组更有价值。因此本文研究的对象将是进化的数据流, 数据流将在衰减窗口模型[4]下进行。
下面给出本文用到的一些名词的定义。
定义1密度给定对象集合D, 对空间中任何一点p及距离ε, 以p为中心, ε为半径的区域内数据点的个数称为点p关于距离ε的密度D (p, ε) 。
定义2核心对象对空间任一点p、距离ε及给定阈值ξ, 若D (p, ε) ≥ξ, 则称p为核心对象。
定义3Nε (q) 邻域每个核心对象q代表了以该点为中心, ε为半径的圆形区域, 即{q∈D|dist (p, q) ≤ε}, 该区域称为核心对象的Nε (q) 邻域。
定义4密度可达存在对象链p1, p2, …, pn, pn=q, 对于pi∈D, 满足D (pi, pi+1) <ε, 称pi+1是从pi关于ε和ξ直接密度可达的。
定义5边界点、噪声不是核心对象, 但在簇中, 即至少从一个核心对象直接可达, 不在任何簇中的点称为噪声。
定义6微簇在t时刻, 假设簇mc中维护了一组带有时间标签Ti1, Ti2, …, Tin的d维数据点集Xi1, Xi2, …, Xin, 此时可用五元组结构特征来对其进行定义, 称簇mc为微簇[5]。
其中矢量分别是每位数据值的平方和及累加和, 如第p维的分别是:
w为权重和, 其值为
t为最后到达该簇的时间;τ反映了该簇为候选核心簇或者是离群核心簇, 当权重w≥βμ时, τ=1, 该簇为候选核心簇, 否则该簇为离群核心簇。
根据以上数据可以得到微簇的中心为:
微簇的半径为:
定义7核心微簇在t时刻, 假设微簇mc中存在一组带有时间标签Ti1, Ti2, …, Tin的d维数据点集Xi1, Xi2, …, Xin, 此时可以用三元组的特征结构CMC (w, c, r) 对其进行定义:
称这种情况下的微簇为核心微簇。其中, 满足w>μ, w为权重, c为中心, r为半径。
2 DDCS-Clustering算法
下面先来介绍一下算法的基本思想, 然后再给出算法具体的执行步骤, 对算法性能进行简要分析, 最后给出完整的DDCS-Clustering算法。
2.1算法的基本思想
DDCS-Clustering算法可分为三个部分:
(1) 局部站点接收数据流, 判断数据流属性, 并进行数据流的预处理;
(2) 微簇在线维护。局部站点针对衰减窗口内的数据流进行处理, 根据窗口周期、权重阈值、半径大小、误差因子和衰减系数等参数来计算数据的权重, 并存储数据流中数据所包含的信息, 动态地更新维护数据流的概要数据结构, 在线生成微簇;
(3) 局部数据上传至中心站点, 在中心站点根据用户请求用DBSCAN算法[6]完成数据流全局聚类。
算法执行的第一步, 分布在一定区域内的局部站点接收数据流, 并对数据流的维数进行判断, 如果不需要降维则直接进行第 (2) 步, 使用衰减窗口截取并存储数据流信息, 根据密度形成中心点集, 进而形成核心微簇, 完成核心对象的聚类。当各个局部站点完成聚类后, 将聚类的结果传送至中心站点, 用DBSCAN形成全局聚类, 满足用户的查询请求。
2.2生成中心点 (GCP) 算法
为了计算对象之间的距离, 必须记录每个中心点的坐标, 中心点并不是实际输入的数据, 而是其对应区域内所有点的代表。在该算法中记录每个中心点的所在区域内所有对象的各个坐标分量之和, 以便更新中心点的坐标。此外需要每个代表区域内的数据点的数目, 为后面的密度做准备。
中心点的选取按如下两个步骤进行: (1) 生成候选中心点集合; (2) 根据阈值大小对中心点集过滤。过滤候选中心点集需要对其进行一次单遍扫描。生成核心对象GCP (Generate CenterPoints) 算法如下:
其中, 判断核心对象是否包含某个数据点为一个Check方法, 该方法的返回值为一个布尔值, 对于核心对象集合c Set, 遍历其中的每一对象, 如果某对象是核心对象, 就将该对象的坐标信息加入到候选对象集, 并返回true, 否则返回false。
2.3局部站点聚类
局部站点数据流处理采用滑动时间窗口模型, 随着时间的推移, 到达的数据流有着不同的权重, 先到达的权重较小, 后到达的权重较大。局部站点之所以采用时间滑动窗口模型, 是因为不必一次性将所有数据载入内存, 只需保存当前时间窗口内的数据即可, 从而节省了内存的开销。
记动态数据流为DS, 时间滑动窗口的周期为Td, 权重阈值为μ, 半径阈值为ε, 误差因子为β, 衰减系数λ。那么局部站点聚类算法描述如下:
(1) 初始化微簇。应用GCP算法生成中心点, 即核心微簇;
(2) 添加数据对象。在窗口Bi中, 对于新到的数据对象p, 若满足rp≤ε, 则将其归入到离群核心簇, 同时修改其数据结构概要为
(3) 建立新的离群核心簇。在离群核心簇中, 若w≥βμ, 即当离群核心簇中某对象的权重大于权重阈值和误差因子的乘积时, 则新建一个离群微簇, 将该对象转移到这个新的离群微簇中;
(4) 微簇衰减。一段时间内没有新的数据到达时, 需要增量更新聚类微簇的特征, 其特征按照衰减函数f=2-λΔt变化, 即
(5) 过期微簇的删除。数据不断到达, 离群核心簇的数量迅速增加, 增大了系统的负载, 同时, 当从滑动窗口中移除历史记录时, 有些微簇的权重可能已经衰减到小于给定阈值, 因此需要对离群或者过期的微簇进行删除。假设当前时刻为tc, 窗口的时间周期为T, 删除周期为Td, 且Td∈[T, 2T) , 则有:
对于微簇mc, 若|mc.t-tc|≥Td, 那么mc属于过期微簇, 应删除。
对于微簇mc, 若|mc.t-tc|
(6) 保存聚类微簇的特征向量。将时间滑动窗口与微簇特征向量保存。
2.4全局聚类
局部站点聚类结束之后, 要将聚类结果传至中心站点进行全局聚类, 本文中全局聚类采用DBSCAN算法, 因为DBSCAN算法在密度聚类中是最为经典的算法, 无论在异常数据处理方面还是在聚类的质量上效果都很好。按照分布式聚类模型, 各个局部站点将聚类的结果上传至主站点, 然后进行全局聚类。由于局部核心对象的聚类半径为ε, 在全局聚类时, 为了避免聚类结果被划分为过多的小类, 需要适当地扩大聚类半径。
设Si表示第i个子站点上的聚类集合, cSeti={ci1, ci2, …, cin}表示该站点上已经确定下来的前n个元素, 第n+1个元素的半径εn+1可以设为εn+1=max{ε1, ε2, …, εn+1}。这时在主站点第i个核心对象pi的查询半径为εpi=ε+εi, 全局聚类算法的伪代码如下:
方法Expand (S, ε, MinPts, Cluster Id, current Obj) 用来判断当前对象current Obj是否为核心对象, 判断的标准仍是和MinPts大小比较, 如果该对象包含的数目大于MinPts, 则形成以current Obj对象为中心的聚类, 并返回true, 否则视current Obj为噪声数据, 函数返回false。
3实验评估
3.1建立实验
本文对DDCS-Clustering算法的聚类质量与通信代价进行实验评估。算法的编程环境为JDK 1.7.0, MyEclipse 6.5 (Blue Edition) , WEKA (Waikato Environment for Knowledge Analysis) 3.7.5[7]以及MOA (Massive Online Analysis) 20111103[8], 操作系统为Microsoft Windows XP。实验在计算机网络实验室3台配置为2.8 GHz Pentium4 CPU以及1GB内存的PC机上进行, 利用实验室的锐捷交换机将三台计算机组建成微型分布式系统。
WEKA是由新西兰怀卡托 (Waikato) 大学开发的智能数据分析软件, 该软件由Java技术开发, 而且代码开源, 遵循GNU General Public License, 是数据挖掘与知识探索与发现领域的一款最为完备的挖掘工具之一。其源代码开源, 开发者可以在其基础上进行修改和创新, 是数据挖掘研究人员必须掌握的一种开发工具。
MOA是一个基于WEKA用Java实现的数据流在线分类、聚类软件平台, 可以实现数据流在线学习、产生仿真数据流并进行算法评估。本实验分析了MOA的源代码, 并在此基础上实现MOA的相关接口, 将本章的算法部署到MOA平台上, 与Clu S-tream等数据流挖掘算法进行了对比。
本实验中所用到的数据流为RandomRBFGenerator (随机径向基函数生成器) 产生的随机数据流, 参数如表1所示。所生成的数据如表2所示, 其值为0至1的双精度类型数据。
MOA数据生成器产生数据流的速度是与计算机软硬件环境直接相关的, 数据维数和噪声是影响数据流的两个重要因素。实验中由于硬件条件所限, 数据流速与噪声比例设得都比较小, 将算法DDCS-Clustering与Clu Stream进行比较分析, DDCS-Clustering算法选取参数为ε=0.01, minPoint=10, β=0.001, μ=1.1, init Point=1 000, window Size=1 000。Clu Stream算法的参数为window Size=1 000, max Num Kernals=80, kernalRad Factor=2。在MOA中主界面如图1所示, 运行界面如图2所示, 图2 (a) 为DDCS-Clustering算法的运行窗口, 图2 (b) 为Clu Stream算法运行窗口。
3.2聚类质量分析
图3为DDCS-Clustering算法与Clu Stream算法在上述参数下的聚类质量分析图。聚类的质量主要体现在聚类的纯度 (Purity) , 该图显示了6 000条实例的聚类纯度, 由图3可以看出, DDCS-Clustering算法的聚类质量最少不低于Clu Stream算法, 从图2中也可以看出, DDCS-Clustering算法对噪声不敏感, 在处理噪声方面也优于Clu Stream。
DDCS-Clustering算法有效的删除机制保证了较高的聚类质量, 在删除噪声点的同时维护了数据流中的潜在微簇, 对潜在微簇进行聚类分析 (核心微簇或者离群微簇) , 而Clu Stream却没有这种机制来区分潜在微簇, 因此浪费了大量的内存来处理噪声。
3.3通信代价分析
实验中共有三台计算机, 其中一台作为主站点, 在此实验中比较了DDCS-Clustering算法与Clu Stream算法的通信代价 (单位为Kbit) , 如图4所示。由图4可以看出, 在分布式环境下, DDCS-Clustering算法的数据流聚类通信代价和Clu Stream算法变化趋势总体上保持一致, 但总体上DDCS-Clustering的通信代价要比Clu Stream低。
4结语
分布式数据流聚类是数据流挖掘中的重要研究内容, 当前的研究仍然面临着很大的挑战, 也有很多的机遇。本文主要介绍了数据流聚类中的若干概念, 提出一种分布式密度和中心点的数据流聚类算法DDCS-Clustering, 通过局部站点数据流聚类和中心站点聚类两个主要步骤完成数据流聚类, 用人工产生数据流模拟数据流进行试验。分析了该算法的聚类质量和通信代价, 证明了该算法的可行性。
参考文献
[1]Minos Garofalakis.Distributed Data Streams.Yahoo!Research and Univ.of California, Berkely[R/OL].http://www.softnet.tuc.gr/~minos/Papers/eds09dstreams.pdf.
[2]Charu C Aggarwal, Han Jiawei, Wang Jianyong, et al.A Framework for Clustering Evolving Data Streams[C]//Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.
[3]Luo Ke, Wang Lin.Data Streams Clustering Algorithm Based on Grid and Particle Swarm Optimization[C]//2009-International Forum on Computer Science-Technology and Applications.
[4]张晓龙, 曾伟.基于衰减窗口与剪枝维度树的实时数据流聚类[J].计算机应用研究, 2009 (4) :1331-1341.
[5]Amineh Amini, The Ying Wah.Density Micro-Clusteirng Algorithms on Data Streams:A Review[C]//Proceedings of the International MultiConference of Engineers and Computer Scientists 2011-Vol I, IMECS 2011, March 16-18, 2011, Hong Kong.
[6]Martin Ester, Hans-Peter Kriegel, Jorg Sander, et al.A Density Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]//Proceedings of 2ndInternational Conference on Knowledge Discovery and Data Mining (KDD-96) .
[7]Aadtiya Desai, Dr.Sunil Rai.Analysis of Machine Learning Algorithms using WEKA[C]//International Conference&Workshop on Recent Trends in Technology, (TCET) 2012, Proceedings published in International Journal of Computer Applications (IJCA) .