下载文档原格式
各种聚类算法的比较聚类算法是一种将数据按照相似性分组的无监督学习方法。
在数据分析和机器学习中，聚类算法被广泛应用于数据挖掘、模式识别、图像处理等领域。
本文将介绍几种常见的聚类算法，并对它们进行比较。
1. K-means算法K-means算法是最常见的聚类算法之一，它将数据划分为K个集群，每个集群包含最接近其均值的数据点。
该算法迭代地更新集群的均值，直到满足收敛条件。
K-means算法简单、高效，适用于大型数据集。
然而，它对异常值和噪声敏感，并且对初始聚类中心的选择非常敏感。
2.层次聚类算法层次聚类算法是一种自底向上或自顶向下的聚类方法，它通过计算数据点之间的相似性构建一个聚类层次结构。
这种层次结构可以以树状图的形式表示，称为树状图聚类。
层次聚类算法的优点是不需要指定聚类个数，且能够处理任意形状的聚类。
然而，该算法的计算复杂度较高，并且对输入数据的规模和噪声敏感。
3.密度聚类算法密度聚类算法通过计算数据点周围的密度来确定聚类结构。
DBSCAN是最常见的密度聚类算法之一，它通过指定半径和邻域密度来定义聚类。
DBSCAN能够识别任意形状的聚类，并且对噪声和异常值具有较高的鲁棒性。
然而，密度聚类算法对参数的选择非常敏感，并且对高维数据和不同密度的聚类效果较差。
4.基于概率的聚类算法基于概率的聚类算法假设数据服从其中一种概率分布，并通过最大化似然函数来进行聚类。
GMM (Gaussian Mixture Model) 是一种常见的基于概率的聚类算法，它假设数据由多个高斯分布组成。
GMM算法能够分离具有不同协方差的聚类，适用于高维数据和非球状的聚类。
然而，该算法对初始参数的选择敏感，并且计算复杂度较高。
5.划分聚类算法划分聚类算法将数据划分为互斥的聚类，然后通过迭代地重新分配数据点来优化聚类质量。
PAM (Partitioning Around Medoids) 和CLARA (Clustering Large Applications)是常见的划分聚类算法。
大数据常用的算法标题：大数据常用的算法引言概述：随着信息时代的到来，大数据已经成为了各行各业的重要组成部份。
在处理大数据时，算法起着至关重要的作用。
本文将介绍大数据常用的算法，匡助读者更好地了解大数据处理过程中常用的算法。
一、聚类算法1.1 K均值算法：K均值算法是一种常用的聚类算法，通过将数据点分配到K 个不同的簇中，使得每一个数据点与其所在簇的中心点的距离最小化。
1.2 DBSCAN算法：DBSCAN算法是一种基于密度的聚类算法，能够发现任意形状的簇。
该算法通过定义核心点、边界点和噪声点来进行聚类。
1.3 层次聚类算法：层次聚类算法是一种树状聚类方法，通过逐步合并最相似的簇来构建聚类树，从而得到不同层次的聚类结果。
二、分类算法2.1 决策树算法：决策树算法是一种常用的分类算法，通过构建树状结构来表示不同类别之间的关系。
该算法易于理解和解释，适合于各种类型的数据。
2.2 支持向量机算法：支持向量机算法是一种二分类模型，通过构建最大间隔超平面来实现分类。
该算法在处理高维数据和非线性数据方面表现出色。
2.3 朴素贝叶斯算法：朴素贝叶斯算法是一种基于贝叶斯定理的分类算法，通过假设特征之间相互独立来简化计算。
该算法在文本分类等领域有着广泛的应用。
三、回归算法3.1 线性回归算法：线性回归算法是一种用于建立变量之间线性关系的回归分析方法。
该算法通过最小化残差平方和来找到最佳拟合直线。
3.2 逻辑回归算法：逻辑回归算法是一种用于处理二分类问题的回归算法，通过将线性回归结果映射到0和1之间来实现分类。
3.3 随机森林算法：随机森林算法是一种集成学习算法，通过构建多个决策树来实现回归和分类任务。
该算法在处理大数据和高维数据时表现出色。
四、关联规则算法4.1 Apriori算法：Apriori算法是一种用于发现频繁项集的关联规则算法，通过逐层搜索频繁项集来发现数据中的关联规则。
4.2 FP-growth算法：FP-growth算法是一种用于挖掘频繁项集的关联规则算法，通过构建FP树来高效地发现频繁项集。
数据分析中的聚类算法在当今数据风暴的时代，海量数据给人们的工作和生活带来了极大的便利，但同时也对我们的数据分析能力提出了更高的要求。
如果我们能够从海量数据中发现其中隐藏的规律和规律，在不断的迭代中，我们可逐步做出更优的决策，从而获得更好的效果和竞争优势。
而聚类算法便是众多数据分析算法中的一种，是一种非监督式学习方法，旨在将数据对象分成若干个互不重叠的类簇，每个类簇中的对象比较相似，而不同类簇之间的对象差异较大。
以下我们将从聚类的基本原理到算法实现的方法进行讲解。
一、聚类算法的基本原理1. 相似性度量聚类算法以相似性度量为基础，也就是通过某些距离、相似性或差异指标来计算数据对象之间的差异程度，然后根据这些度量标准将不同的对象分到不同的类别中。
一般来说，相似性度量可以通过欧式距离、曼哈顿距离、余弦相似性等方式来实现，选择哪种方法取决于数据的特点和需求。
2. 类划分准则聚类算法的目标是将数据对象分成若干个互不重叠的类，不同的类之间相似度较低。
类划分准则是指在相似性度量的基础上，通过某些自定义规则或指标来进行类的划分。
例如，常见的划分准则有最小距离法、最大距离法、平均距离法等。
3. 类中心表示聚类算法需要对划分出的每一个类进行表示，也就是通过某些方式来描述每一个类的中心、半径、密度等。
因为类中的数据对象最好是以某种数学中心来表示，这样如果我们需要针对这一类进行一些数据统计，可以方便地计算每个类的中心值和离差，进行数据分析和决策。
二、聚类算法的主要流派1. 划分聚类算法划分聚类算法是指先初始化一些聚类中心点，然后通过迭代过程不断将数据对象划分到最优的聚类中心点上。
其优点是计算效率高、实现简单，但其缺点也很明显，就是对聚类中心点的选择非常敏感，可能会导致分类结果波动较大，难以保证分类结果的准确度。
最常用的划分聚类算法是 k 均值聚类算法，它是一种通过不断迭代的方式不断调整聚类中心点位置的算法，例如：假设我们想将数据分为 k 类，首先需要随机选择 k 个中心点，然后通过计算每个数据对象和 k 个中心点之间的距离来确定每个对象所属的类别，直到聚类中心点不再变化或达到预先设定的迭代次数为止。
聚类算法——DBSCAN算法原理及公式聚类的定义聚类就是对⼤量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较⼤⽽类别间的数据相似度较⼩。
聚类算法是⽆监督的算法。
常见的相似度计算⽅法闵可夫斯基距离Minkowski/欧式距离在上述的计算中，当p=1时，则是计算绝对值距离，通常叫做曼哈顿距离，当p=2时，表述的是欧式距离。
杰卡德相似系数(Jaccard)杰卡德相关系数主要⽤于描述集合之间的相似度，在⽬标检测中，iou的计算就和此公式相类似余弦相似度余弦相似度通过夹⾓的余弦来描述相似性Pearson相似系数相对熵(K-L距离)相对熵的相似度是不对称的相似度，D(p||q)不⼀定等于D(q||p)。
聚类的基本思想给定⼀个有N个对象的数据集，划分聚类的技术将构造数据的K个划分，每个划分代表⼀个簇，K<=n。
也就是说，聚类将数据划分为k个簇，⽽且这k个划分满⾜下列条件：每个簇⾄少包含⼀个对象，每⼀个对象属于且仅属于⼀个簇。
具体的步骤为，对于给定的k，算法⾸先给出⼀个初始的划分⽅法。
以后通过反复迭代的⽅法改变划分，使得每⼀次改进之后的划分⽅案都较前⼀次更好。
密度聚类密度聚类⽅法的指导思想是，只要⼀个区域中的点的密度⼤于某个阈值，就把它加到与之相近的聚类中去。
这类算法能够克服基于距离的算法只能发现“类圆形”的聚类的缺点，可以发现任意形状的聚类，且对噪声数据不敏感。
但计算密度单元的计算复杂度⼤，需要建⽴空间索引来降低计算量。
DBSCAN算法DBSCAN是⼀个⽐较有代表性的基于密度聚类的聚类算法，它对簇的定义为密度相连的点的最⼤集合，能够把具有⾜够⾼密度的区域划分为簇，并可在有噪声的数据中发现任意形状的聚类。
DBSCAN相关定义对象的ε-邻域：给定对象在半径ε内的区域。
核⼼对象：对于给定的数据m，如果⼀个对象的ε-邻域⾄少包含有m个对象，则成为该对象的核⼼对象。
直接密度可达：给定⼀个对象集合D，如果p是在q的ε-邻域内，⽽q是⼀个核⼼对象，则对象p从对象q出发是直接密度可达的。
聚类算法的概念聚类算法是一种无监督学习的算法，用于对数据集进行分组或聚类。
聚类算法的目标是将相似的数据点聚集到一起，同时将不相似的数据点分开。
这可以帮助我们对数据进行更好的理解和分析，以及发现其中的模式和结构。
聚类算法适用于许多应用领域，例如市场和客户分析、医学图像分析、社交网络分析等。
聚类算法可以帮助我们识别有趣的子集，发现重要特征，提高数据可视化和探索性分析。
聚类算法通常分为分层聚类和非分层聚类两种类型。
在分层聚类中，我们会先生成一个聚类层次结构，然后根据需要将层次结构划分为不同数量的簇。
在非分层聚类中，我们不必生成层次结构。
聚类算法的核心思想是在数据空间中计算数据点之间的相似度。
这样可以将相似的数据点放在一起，然后分离不同的群体。
常见的相似度度量包括欧式距离、余弦相似度和曼哈顿距离等。
相似度通常使用矩阵表示，称为相似度矩阵。
聚类算法通常包括以下步骤：1. 选择一个合适的相似度度量。
这取决于数据类型和问题的需求。
2. 选择一个聚类算法。
其中一些经典的算法包括k-均值聚类、层次聚类、DBSCAN 等。
3. 确定聚类的数量。
通常需要手动或基于一些评估准则来选择最佳聚类数量。
4. 将数据集分成不同的聚类。
在聚类算法中，k-均值聚类是最广泛使用的算法之一。
K-均值聚类通过选择k个中心点，然后将每个数据点分配到离它们最近的中心点所在的簇中进行操作。
在执行过程中，中心点会不断被更新，直到达到最优聚类结果。
层次聚类是另一种常见的聚类算法。
它从单个数据点开始，逐渐聚集更多的数据点，形成一个层次结构。
层次聚类可分为聚合和分裂两种类型。
聚合层次聚类将每个数据点都视为一类，然后逐渐合并相似的簇。
而分裂层次聚类是从单个大簇开始，不断分裂成更小的簇。
DBSCAN也是一个流行的聚类算法，它可以在数据中识别任意形状的簇。
DBSCAN基于密度，即在足够密集的区域中聚集数据点，并将其与低密度区域分开。
综上所述，聚类算法是一种强大的机器学习技术，可以用于数据集的探索性分析和处理。
聚类算法：K-Means和DBSCAN的比较聚类算法是一种机器学习方法，它可以将数据分成不同的群组或类别。
这些算法在大数据分析、图像处理、模式识别等领域都有着广泛的应用。
其中，K-Means和DBSCAN是两种常用的聚类算法，它们有着各自的特点和适用范围。
在本文中，我将对K-Means和DBSCAN进行比较，探讨它们的优势和劣势，以及适用场景。
1. K-Means算法概述K-Means算法是一种基于中心的聚类算法，它将数据集划分为K个非重叠的子集，每个子集代表一个簇。
该算法的基本思想是通过迭代的方式，将数据点划分到最近的簇中，并更新每个簇的中心位置，直到收敛。
K-Means算法的流程如下：1）随机初始化K个中心点；2）将每个数据点划分到距离最近的中心点所对应的簇中；3）计算每个簇的中心点，并更新中心点的位置；4）重复步骤2和3，直到中心点位置不再发生变化，算法收敛。
K-Means算法的优点包括简单、易于实现、计算速度快等，但也存在一些缺点，比如对初始中心点位置敏感、对异常值敏感等。
2. DBSCAN算法概述DBSCAN算法是一种基于密度的聚类算法，它能够发现任意形状的簇，并且对噪声点不敏感。
该算法的基本思想是以每个数据点为中心，在其邻域内寻找密度满足要求的点，从而构建簇。
DBSCAN算法的流程如下：1）选择两个参数：邻域大小和最小包含点数；2）随机选择一个未被访问的数据点；3）检查该点的邻域内是否包含足够多的点，如果是，则将该点标记为核心点，并将其邻域内的点都加入当前簇；4）重复步骤2和3，直到所有点都被访问。
DBSCAN算法的优点包括能够发现任意形状的簇、对噪声点不敏感等，但也存在一些缺点，比如对参数敏感、需要对距离进行计算等。
3. K-Means和DBSCAN的比较K-Means和DBSCAN是两种经典的聚类算法，它们在应用场景、优缺点等方面有着一定的差异，下面我将对它们进行详细的比较分析。
singlepass聚类算法
Single-pass聚类算法，也被称为增量式聚类算法，是一种基于
数据流的聚类算法。
与传统的聚类算法不同，Single-pass聚类
算法只需扫描一次数据流，即可对数据进行聚类。
Single-pass聚类算法的基本思想是在数据流中逐个处理数据项，根据预定的聚类准则将每个数据项分配到适当的聚类中。
根据数据的流动性质，可以动态更新聚类模型，避免了对整个数据集进行运算的复杂性。
Single-pass聚类算法有多种实现方式，其中最经典的是基于领
域的聚类方法（基于密度、距离等准则）。
算法首先初始化一个空的聚类模型，然后依次处理每个数据项。
对于每个数据项，算法根据其与现有聚类的距离或密度等准则，将其分配到合适的聚类中，或者创建一个新的聚类。
Single-pass聚类算法的优点是简单且具有较好的效率，适用于
大规模数据流处理和实时聚类分析。
然而，由于只有一次扫描数据流，算法对初始聚类模型的依赖较大，可能存在一些局部最优的问题。
因此，在实际应用中需要根据具体情况选择合适的聚类算法。
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.17, No.3, March 2006, pp.379−387 DOI: 10.1360/jos170379 Tel/Fax: +86-10-62562563© 2006 by Journal of Softwar e. All rights reserved.∗基于数据流的任意形状聚类算法朱蔚恒+, 印鉴, 谢益煌(中山大学计算机科学系,广东广州 510275)Arbitrary Shape Cluster Algorithm for Clustering Data StreamZHU Wei-Heng, YIN Jian, XIE Yi-Huang(Department of Computer Science, Sun Yat-Sen University, Guangzhou 510275, China)+ Corresponding author: E-mail: gz_zwh@, Zhu WH, Yin J, Xie YH. Arbitrary shape cluster algorithm for clustering data stream. Journal of Software,2006,17(3):379−387. /1000-9825/17/379.htmAbstract: CluStream is a popular data stream cluster algorithm, however, it is not capable enough to clusterarbitrary shapes and make clusters in periodic data. This paper introduces a new algorithm ACluStream to solvethese problems. The ACluStream is based on the partition and assemble of the space and cluster by density. In theexperiment, it is shown that ACluStream is better than CluStream in speed and accuracy.Key words: data stream; clustering; data mining摘要: 详细分析了数据流聚类算法CluStream的不足之处,如对非球形的聚类效果不好、对周期性数据的聚类变化反映不完整等,并针对这些不足之处提出了一种采用空间分割、组合以及按密度聚类的算法ACluStream.实验结果表明,ACluStream在准确度和速度上都比CluStream有较大的提高.关键词: 数据流;聚类;数据挖掘中图法分类号: TP311文献标识码: A近年来,由于硬件技术的高速发展,人们获取数据的能力得到了极大的提高.现实生活中,经常可以看到这样的情况:大量需要处理的数据以很快的速度产生.例如,美国一条高速公路上的传感器网络每天可以收集到高达几百万条的数据,而电讯电话公司大型交换机上每天记录的通话记录就高达几千万条.由于数据量太大、数据产生的速度太快,按传统的数据库应用模式处理这些数据,即完整、详细地收集这些数据,清洗后将其储存在数据库中,再交由计算机仔细处理已成为不可能完成的任务.由有限的数据到有限的数据处理能力,计算机工作者们面临着新的挑战.∗ Supported by the National Natural Science Foundation of China under Grant No.60573097 (国家自然科学基金); the ResearchFoundation of National Science and Technology Plan Project of China under Grant No.2004BA721A02 (国家科技计划); the ResearchFoundation of Disciplines Leading to Doctorate Degree of Chinese Universities under Grant No.20050558017 (高等学校博士学科点专项科研基金); the Natural Science Foundation of Guangdong Province of China under Grant Nos.05200302, 04300462 (广东省自然科学基金); the Research Foundation of Science and Technology Plan Project in Guangdong Province of China under GrantNo.2005B10101032 (广东省科技计划项目)Received 2004-09-28; Accepted 2005-03-11380 Journal of Software软件学报 V ol.17, No.3, March 2006针对如何分析管理这种大量快速的数据问题,人们提出了一类新型应用作为解决方案.这些方案最大的特点是,待处理的数据不再静态、固定地存储在可多次、随机访问的介质中,而是以一种动态、流式的形式出现(并称其为数据流,data stream),对数据只能是顺序的、一次或有限次的访问[1].在最近的研究中,数据流已逐渐成为新一代计算理论与应用的研究热点之一.与传统的数据库应用相比,应用于数据流的算法有几个明显的特点:首先,由于数据流的速度很快,对算法的响应要求很高,所以数据流算法经常采用用精度换时间的方法,尽量在对数据的一次访问中获得较优的解.一般来说,数据流算法是不可回溯的;其次,数据流算法有很多特点,一些数据库应用中常用的操作在数据流中都是不可行的.如,Sort,Max,Count等Blocking操作[2].目前对数据流的研究主要集中在以下几个方面:对数据流工作模型的建模、对数据流查询的响应、如何管理数据流、如何对数据流进行挖掘等.在数据流挖掘方面,如何在数据流中进行有效聚类,是一个吸引了研究者很大注意力的问题[3−6].2000年,Guha提出针对数据流聚类的LOCALSEARCH[5]算法.算法的基本思想是基于分治的思想使用一个不断的迭代过程实现有限空间对数据流进行k-means聚类.O’Callaghan发展了LOCALSEARCH的思想.他于2002年提出了STREAM[6]算法,并利用SSQ证明了在多种情况下,STREAM算法的聚类效果都比BRICH[7]算法要好.但LOCALSEARCH和STREAM方法都有一个缺点,即只能提供对当前数据流的一种描述,而不能反映流数据的变化情况[4].2003年,Barbard总结了数据流聚类算法的要求[3],并对一些可能适用于数据流的聚类算法做了一次总结.他认为在数据流中聚类要满足3个要求:(1) 压缩的表达;(2) 快速、增长地处理新的数据点;(3) 快速、清晰地判断独异点.CluStream[4]是Aggarwal在2003年提出的一个解决数据流聚类问题的框架.它使用了两个过程来处理数据流聚类问题:首先,使用一个在线的micro-cluster过程对数据流进行初级聚类,并按一定的时间跨度将micro-cluster的结果按一种称为pyramid time frame的结构储存下来.同时,使用另一个离线的macro-cluster过程,根据用户的具体要求对micro-cluster聚类的结果进行再分析.本文第1节分析CluStream算法存在的一些问题,并简要介绍我们提出的新算法ACluStream所使用到的基本概念和一些关于ACluStream的理论证明.第2节给出一个完整的ACluStream算法,详细解析算法的思想和执行过程.第3节给出ACluStream与CluStream具体的实验比较,可以看到与CluStream相比,ACluStream具有很强的空间表达能力.最后,讨论ACluStream的不足以及继续研究的方向.1 问题分析与算法概述1.1 CluStream存在的问题CluStream提供了一个解决数据流中聚类问题的框架,虽然该框架非常优秀,但在这个框架中仍有许多可以改进的地方.CluStream使用了一个在线的micro-cluster过程对数据流进行初级描述,后续工作都是建立在该过程的输出之上.显然,这个过程是整个聚类算法的基础,但CluStream所使用的micro-cluster过程的存在一些不足.micro-cluster过程使用的是类似BRICH算法所使用的聚类特征值来记录它所产生的子聚类.BRICH算法的缺点必然也带入micro-cluster过程中.BRICH算法记录聚类特征值的方法对球型的聚类效果好,但对其他形状的聚类,BRICH不能很好地工作[8].所以对非球形的聚类,micro-cluster过程同样不能给出一个很好的描述.由于micro-cluster过程得到的结果是对数据流进行一个初步的描述,所以,如果这个描述本身不精确,那么后续的macro-cluster过程将不能得到一个较好的结果.再观察micro-cluster对新数据的处理:它利用数据与最近子聚类中心的距离以及一个预定的距离阈值来判断数据是否属于该子聚类.但距离某一聚类中心近的点不一定就属于该聚类.观察如图1所示的例子.朱蔚恒 等:基于数据流的任意形状聚类算法381图1中的点集属于两个不同的类别,使用micro-cluster 过程进行聚类时,由于各数据点生成次序的不同,最后得到的聚类结果可能有多种.其中一种就是生成图1中使用圆圈标出的两个子聚类.显然,这两个子聚类并不能准确区分两个类别,而且它们所覆盖的面积比原来点集的面积几乎大了一倍.此方法在处理流数据时还会造成各子聚类所覆盖的区间重叠,同一位置的点被归入不同的子聚类的情况.更进一步地,micro-cluster 判断一个新来的点是否属于某子聚类的方法是根据该点与子聚类中心的距离.因为子聚类没有严格的空间定义,它的中心随着每一个点的到来而发生改变.所以,不能保证生成子聚类的点最后都包含在一个与子聚类中心距离不大于r 的圆形邻域中.可以证明,在最坏情况下,子聚类初始部分的点与子聚类中心的距离可能是无限远.Fig.1 A bad cluster 图1 一个不好的聚类针对上述问题,本文提出了基于密度与空间的ACluStream(arbitrary-shape CluStream)聚类算法.算法的目标是在对数据流进行初步聚类的同时,尽量保留数据的空间特性.ACluStream 算法采用了与CluStream 相同的架构:采用两个过程处理数据,一个在线的过程给出对当前数据流特征的描述,按pyramid frame 的结构储存这些描述;一个离线的过程利用这些描述处理查询. 1.2 ACluStream 使用的基本概念定义n 维空间S 上点集D .D 中的元素以数据流的形式到达.算法的目标是按到达的顺序得到D 中某一批数据的一个聚类描述.为解决这个问题,引入一个空间块的概念:对n 维空间Space n 中的各维定义一个最小跨度,记为d step _i .一个空间块就是多维空间中的由两个n 维向量(d begin ,span )确定的区间,d begin 对应n 维空间中的一个点,称为起始点,d begin 在各维上的投影为该维最小跨度的一个倍数,即d begin i =n ×d step _i .span 为n 维向量,称为边长表,每一维上的投影同样也是该维最小跨度的一个倍数.一个空间块(d begin ,span )就是一个以d begin 为起点、向各维的正方向延伸span 中对应维长度的一个区间.对二维平面而言,一个空间块就是一个矩形.对三维立体空间而言,一个空间块就是一个长方体.由空间块的定义可知,对n 维空间Space n ,可以构造Space n 的一个划分{(d 0,d span ),…,(d i ,d spani ),…}.其中(d i , d spani )代表n 维空间Space n 中两两互不相交的空间块.由空间块的概念和基于密度聚类的思想,引入另一个概念——聚类块.定义变量ρ,称之为密度.一个聚类块就是n 维空间Space n 上的一个空间块block (d begin ,span ),block 中包含n 个数据点,n ≥ρ×.1∏=ni i span 在ACluStream 算法中,子聚类是以聚类块的形式记录的. 1.3 ACluStream 完备性和可行性的证明首先证明完备性:使用聚类块结构能够完整地近似表达任意的空间形状.当假设数据流的数据具有某种空间特征(由一个特定函数f (x )决定),由Riemann 积分的几何意义可知,可以把数据流的形状表达问题看成一个多维空间中的图形求体积的问题,即f (x )的Riemann 积分近似求解问题.同时,根据数值积分的蒙地卡罗方法(Monte Carlo method)得知,可以通过一些相互独立的变量来近似计算欧氏空间中任意函数的定积分,误差范围由样本的数目决定.如对二维欧氏空间,定积分的蒙地卡洛公式为()()()∑∫∫=−−≈Ni i i b a d cX X f N c d a b X X X X f 121 2121,)(d d ,. 也就是说,对由函数决定,在某一区间上大量均匀分布、相互独立的变量,其和的均值近似等于定义区间上该函数的积分.所以,当聚类块各维的最小跨度d i _step 足够小时,可以认为这种基于聚类块的空间结构可以近似地表382Journal of Software 软件学报 V ol.17, No.3, March 2006达这个n 维空间中的任意形状.下面再证明对于任意的聚类形状,如果使用CluStream 中micro-cluster 过程计算要消耗的空间复杂度为O (S ),那么最坏情况下,可以使用一个空间复杂度为k ×O (S )的聚类块来表达这个聚类形状.Micro-Cluster 通过使用多个最大半径为r 的球形空间子聚类来表达空间聚类.考虑到聚类块的空间意义,显然,最坏情况下,聚类的实际形状就是一个半径为r 的球形.micro-cluster 只需使用一个子聚类,就能完整地描述该聚类.下面证明,只需使用k 个聚类块就可以表达这个球形.设各维的步长为δi ,那么,最多只要使用∏−=11)/(n i i r δ个块,就可以表达覆盖这个球形的一个正方体.显然,当n ,r 和δi 确定的时候,是一个常数,不妨∏−=11)/(n i i r δ将其记为k .也就是说,只要使用小于k 个的空间块就可以表达这个球形.所以,即使最坏情况下,算法的空间复杂度也只是CluStream 的一个线性函数. 1.4 聚类块内对聚类的表达每一个聚类块使用一个聚类块特征值来表示.聚类块特征值是聚类特征值的一个扩充,它使用一个7元组 (2CF ,1CF ,0CF ,t 2,t ,d begin ,span )来标识聚类块在空间中的位置和聚类块中点的分布以及聚类块中点到达的情况.其中,0,1,2分别对应于聚类块中点集的数目、算术和以及各维向量的平方和,即统计学上的零阶矩、一阶矩、二阶矩,特别地,将1CF /0CF 称为聚类块的聚类中心;t ,t 2分别表示聚类块中数据点到达时间的和及平方和,d begin 表示该聚类块的起始点,span 代表该聚类块的体积. 1.5 ACluStream 算法简述ACluStream 算法首先积累一定的数据,然后使用任意的聚类算法对它们进行聚类,再把聚类的结果划分成一个个互不相交的聚类块.记录这些聚类块的特征值向量并使用一个hash 表H 来记录指向这些向量的指针.然后对每一个新来的数据点d ,如果它属于一个聚类块,那么将其加入该聚类块中,并修改该聚类块的特征值;否则,判定它是否为孤立点.当积累的数据量达到窗口大小时,对内存中的聚类块进行分析,根据实际情况或者结合、或者分解,并将保存在内存中的聚类块特征按pyramid frame 的结构记录下来,便于后续查询.2 ACluStream 算法与CluStream 相同,ACluStream 也分为两个部分:在线的进程和离线的进程.记录当前数据流特征的在线进程称为sdmicro-cluster;而离线的响应查询的进程称为sdmacro-cluster.下面详细介绍两个进程各自的工作. 2.1 sdmicro-cluster 过程sdmicro-cluster 过程使用下面3个参数:P guess ,W ,D clu .P guess 为判断一个点是否为新聚类的概率,取值范围为0~1之间的一个实数;W 是数据窗口的大小,取值范围为大于0的整数;D clu 为大于0的整数,是聚类块的最小密度,代表对W 个数据,在单位空间中至少要包含数据点的数目.∏=ni i step d 1_算法描述如下:对每一个新来的点,先计数,然后进行下面的处理.如果它属于一个现有的聚类块(这可以很容易地由各个邻近的聚类块的起始点以及聚类边界确定),那么修改该聚类块的聚类块特征值;否则,这个点或者属于一个新的聚类块,或者是一个独异点.为了节省算法消耗的空间,借鉴数据流中频繁度计算的著名算法STICKY count [9]的思想,使用一种类似“抛硬币”的方法来猜测是否为该点创建一个新的聚类块:在0~1之间取一个随机数,然后判别它是否比预设的参数P guess 要小:如果是,那么假设这个点属于一个新的聚类,为它创建一个新的聚类块;否则,认为该点是一个独异点,将它抛弃.朱蔚恒 等:基于数据流的任意形状聚类算法 383创建一个新的聚类块的过程如下:分配内存中的一个空间,在这个空间中记录一个聚类块的特征.然后,根据聚类块的起点在hash 表H 的相应位置记录指向该空间的指针.当数据流积累到窗口已满的时候,对内存中的聚类块进行下面的运算: (1) 计算新的密度参数基于密度的聚类有一个特点,需要预定义聚类的密度.算法使用一个随数据流规模线性递增的密度函数来计算参数,每次数据窗口满了以后,D clu 参数自动增长.(2) 聚合相邻的、相似的聚类块为节省系统运行的空间消耗,当数据窗口已满时,聚合相邻的、相似的聚类块.为了确保聚类块足够精确,对聚类块的大小有最大限制,只有当聚类块聚合后仍然满足最大限制时才允许其聚合.首先判断该聚类块的密度是否还符合定义.如果聚类块的密度超过D clu 的阈值,那么利用hash 表H 计算是否有可以结合的聚类块:如果存在这样的聚类块,且结合后的大小合适,那么将这些聚类块结合并修改聚类块特征值;否则,访问下一个聚类块.(3) 切割、压缩达不到密度标准的聚类块如果直接抛弃密度小于D clu 的聚类块,那么对一些周期性数据流会产生震荡的效果.算法对聚类块中的特征值的时间维度和密度联合考虑,只有当最近一段时间,该聚类块密度的增长低于密度函数的增长60%时才 抛弃.对密度小于D clu 又达不到抛弃标准的聚类块,再进一步地判断是否可以对该聚类块进行压缩或分割.由于在每个聚类块中记录了聚类的特征值,通过利用这些特征值,可以在每一维精确地计算方差.如果在某一维上的方差超过某一阈值S ,且该维上的聚类中心1i CF 与聚类块中心d begin _i +21span _i 的偏离度较大,那么对该维进行切割:把该聚类块分成两块,保留聚类中心点所在的一块,适当修改聚类特征值;否则,若聚类中心与聚类块中心紧密结合在一起,而且在该维上数据的方差不大,那么以一个合理的尺度在该维上收缩聚类块的大小,修改聚类特征值.(4) 储存内存中的聚类块特征CluStream 每隔一段时间就储存内存中记录的所有子聚类及其特征,称之为snapshot,并按pyramid time frame 的策略组织这些snapshot.Pyramid time frame 是一种按时间来组织数据流的初步描述的策略,它保证了对一个用户定义的时间窗h ,在当前时间的2h 窗口内至少存在一个snapshot.ACluStream 同样采取pyramid frame 结构储存数据,关于pyramid frame 的思想和具体做法可见文献[4]. 2.2 sdmacro-cluster 过程sdmicro-cluster 得到的结果以pyramid frame 结构储存在磁盘上.然后使用sdmacro-cluster(shape density macro-clusterstream)过程响应查询.sdmacro-cluster 的作用就是比较两个不同时间的结果.CluStream 使用对子聚类编号的方法来实现子聚类的标认,并据此判断子聚类的变化.但在AcluStream 算法中,由于聚类块有严格的空间意义,因此不需要对其进行额外的编号.由于sdmacro-cluster 的相对独立,可采取任意一种支持加权聚类的算法来进行.本文对此并不作详细讨论. 2.3 算 法sdmicro-cluster(P guess ,W ,D clu ,Datastream ){先积累一段时间的数据流于滑动窗口,然后用基于密度的方法对数据流聚类,并将聚类结果划分为互不相交的聚类块.For (不到数据流末尾){For(i =0;i <w ;i ++){ 读数据流中的一个点;384 Journal of Software软件学报 V ol.17, No.3, March 2006根据点的位置以及数据块在各维上的最大长度,利用hash表搜索是否存在一个包含这个点的聚类块;if (exist){修改此聚类块特征;}else{if(P guess<getrandom())为该点创建一个聚类块,并将其加入hash表;}}按累计数据的规模重新计算密度函数D clu;按hash表中顺序扫描内存中的聚类块{if (块内密度≤D clu){if (块内密度大于可抛弃的密度){切割或收缩该块;}else{释放该聚类块的空间;};}else{if (exist(可聚合的聚类块)){聚合}}}按pyramid frame的结构储存数据;}}3 算法性能为了比较CluStream,ACluStream的聚类效果,我们分别按照2幅800×600的位图构造数据流,并根据一定比例随机生成噪声点以作为数据源.然后,使用相同大小、数目的子聚类来对数据流进行聚类.当在线程序处理了1 000 000个数据点后,分别比较两种算法聚类形状、聚类质量以及算法的运行速度.3.1 数据流的形状比较使用以下两幅图来生成数据流.实验数据流按图2中的两幅图形的分布随机生成,并按10%的比例生成噪声点.(a) Picture 1(b) Picture 2(a)(b)(a)数据源1 (b)数据源2Fig.2 The pictures for generating the data图2 实验数据源产生数据源1的图是两个表情不同的猩猩头像,这两个头像分别标注为(a)和(b).可以通过它来比较两种算法在处理现实图形数据时的区别.产生数据源2的图是一幅由多种几何图形组成的图片.通过它来比较两种算法在处理几何图形数据时的区别.由于CluStream算法的聚类效果对子聚类数目和子聚类的面积十分敏感,实验中分别采取了多种不同的子聚类数目及半径.多次实验比较的结果证明,ACluStream算法的聚类结果要优于CluStream的聚类结果.由于篇幅所限,这里只给出实验中子聚类数最多、半径最小时的实验结果.这次实验中,取子聚类的最大面积为18,数据源1共使用了9 293个聚类块,数据源2共使用11 895个聚类块.图3、图4展示了两种算法的实验结果,其中图的左半部分是ACluStream算法得到的结果,右半部分是CluStream算法得到的结果.朱蔚恒 等:基于数据流的任意形状聚类算法 385(a)(b)(a)(b)Fig.3 Comparison of accuracy in picture 1’s data图3 数据源1的实验结果由图3的实验结果可以直观地看到:在对真实图像表达能力方面,尤其在对一些细节的描述上,ACluStream 优于CluStream.观察猩猩伸舌头的动作以及标注(a),(b),它们在ACluStream 的结果中基本还原,但在CluStream 结果中就有较大的失真.Fig.4 Comparison of accuracy in picture 2’s data图4 数据源2实验结果由图4的实验结果可以直观地看到:在几何图像表达能力方面,尤其在处理一些间距比较密的线条时,ACluStream 也明显优于CluStream.下面,使用量化的数据来比较两个算法得到的结果.对两幅图G 1,G 2的相似度定义为:在G 1,G 2取值相同的坐标所占图形面积的比例.图5是所作实验的一些比较结果.横坐标表示所使用的聚类的不同精度,纵坐标表示聚类结果的相似度.AclustreamCLUSTREAMAclustreamCLUSTREAMR e s e m b l e d e g r e e1.000.950.900.850.801.000.950.900.85R e s e m b l e d e g r e e8 809 6 074 7 785 5 269Numbers of blocksNumbers of blocks Comparison of resemble degree in picture 1’s dataComparison of resemble degree in picture 2’s dataFig.5 Comparison of resemble degree in experimental data图5 ACluStream 与CluStream 相似度比较3.2 聚类质量比较SSQ(sum of square distance)是一种比较k -划分聚类质量的方法,它通过计算所有点到各自的聚类中心的距离来衡量算法所给出的k -划分的质量.SSQ 值越小,说明算法聚类质量越好.我们使用k -means 方法作为ACluStream 算法和CluStream 算法的离线聚类过程来比较两个程序的初始聚类质量,然后比较两个程序算出的SSQ 值.有趣的是,虽然ACluStream 采用一个基于密度的方法来对数据进行初步聚类,但使用它却得到更好的结果.继续上面实验的比较,如图6所示.386Journal of Software 软件学报 V ol.17, No.3, March 2006AclustreamCLUSTREAMAclustream Mil. CLUSTREAMMil.16.015.515.014.514.0S S QS S Q8 809 6 074 7 785 5 269Numbers of blocks 11 475 8 071 10 429 7 262Numbers of blocksComparison of SSQ in picture 1’s dataComparison of SSQ in picture 2’s dataFig.6 Comparison of SSQ in experimental data 图6 ACluStream 与CluStream 的SSQ 值比较3.3 算法速度比较最后比较算法的运行速度.从本文的第2节对micro-cluster 过程的分析可知,对程序的效率影响主要有两方面的原因:(1) 对用于初步记录聚类信息的子聚类数据结构而言,每当一个新点到达时,其聚类中心点都会改变,需要修改索引;(2) 由于算法的限制,会频繁地出现子聚类聚合和增删操作,从而降低了程序的效率.而ACluStream 算法采用严格的空间定义,所以很容易地就建立了HASH 索引,这个索引相对稳定,只有当数据窗口已满,有聚类块需要切割/合并时才需要对所涉及的聚类块进行修改,极大地提高了程序的效率.所以两个程序在处理数据速度上有很大的差别.进行算法速度测试的具体运行环境是:pIII 700 cpu,256m ddr ram 操作系统为win2k server,下面是程序运行的结果(如图7所示).Fig.7 Comparison of time consume in experimental data图7 ACluStream 与CluStream 运行速度比较4 结论与进一步研究的方向实验结果显示,当ACluStream 使用聚类块与CluStream 子聚类数目相同、最大面积相等时,无论是时间效率还是准确性,ACluStream 算法都比CluStream 要好.不过,无论是CluStream 还是ACluStream 算法,它们都是基于欧氏空间的算法.而且仔细分析算法的流程可以发现,它们都利用了欧氏空间距离的一些特性,不太适合解决非欧氏空间的问题.如何对非欧氏空间的数据流(文本流、多媒体流)进行高效的聚类分析,将是我们下一步工作的方向. References :[1] Golab L, Özsu MT. Issues in data stream management. SIGMOD Record, 2003,32(2):5−14.[2] Babcock B, Babu S, Datar M, Motwani R, Widom J. Models and issues in data stream systems. In: Proc. of the 21st ACMSIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems. 2002. 1−16.[3] Barbará D. Requirements for clustering data streams. ACM SIGKDD Explorations Newsletter, 2003,3(2):23−27. [4] Aggarwal C, Han J, Wang J, Yu PS. A framework for clustering evolving data streams. In: VLDB 2003. 2003. 81−92. [5] Guha S, Mishra N, Motwani R, O’Callaghan L. Clustering data streams. In: FOCS 2000. 2000. 359−366.AclustreamComparison of time consume in picture 1’s dataNumbers of blocksCLUSTREAMAclustreamCLUSTREAMNumbers of blocksComparison of time consume in picture 2’s data朱蔚恒等:基于数据流的任意形状聚类算法387[6] O’Callaghan L, Mishra N, Meyerson A, Guha S. Streaming-Data algorithms for high-quality clustering. In: ICDE Conf. 2002.685−704.[7] Zhang T, Ramakrishnan R, Livny M. BIRCH: An efficient data clustering method for very large databases. In: SIGMOD’96. 1996.103−114.[8] Han J, Kamber M. Data Mining-Concepts and Techniques. Beijing: Higher Education Press, Morgan Kaufmann Publishers, 2001.[9] Manku GS, Motwani R. Approximate frequency counts over data streams. In: VLDB 2002. 2002. 346−357.朱蔚恒(1976−),男,广东广州人,博士生,主要研究领域为数据流挖掘,数据流应用.谢益煌(1981−),男,硕士生,主要研究领域为数据挖掘.印鉴(1968−),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为数据挖掘,机器学习.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@全国首届语义Web与本体论学术研讨会(SWON 2006)征文通知全国语义Web与本体论学术研讨会（SWON）是中国计算机学会电子政务与办公自动化专委会主办的系列会议。
