下载文档原格式
常⽤的聚类算法及聚类算法评价指标1. 典型聚类算法1.1 基于划分的⽅法代表：kmeans算法·指定k个聚类中⼼·（计算数据点与初始聚类中⼼的距离）·（对于数据点，找到最近的{i}ci(聚类中⼼)，将分配到{i}ci中）·(更新聚类中⼼点，是新类别数值的均值点)·（计算每⼀类的偏差）·返回返回第⼆步1.2 基于层次的⽅法代表：CURE算法·每个样本作为单独的⼀个类别··合并,为·遍历完本次样本，合并成新的类别后，若存在多个类别，则返回第⼆步·遍历完本次样本，合并成新的类别后，若所有样本为同⼀类别，跳出循环，输出每层类别1.3 基于⽹格的⽅法代表：STING算法·将数据集合X划分多层⽹格结构，从某⼀层开始计算·查询该层⽹格间的属性值，计算属性值与阈值的关系，判定⽹格间的相关情况，不相关的⽹格不作考虑·如果⽹格相关，则进⼊下⼀层的相关区域继续第⼆步，直到下⼀层为最底层·返回相关⽹格结果1.4 基于密度的⽅法代表：DBSCAN算法·输⼊数据集合X，随机选取⼀点，并找出这个点的所有⾼密度可达点·遍历此点的所有邻域内的点，并寻找这些密度可达点，判定某点邻域内的点，并寻找这些点密度可达点，判定某点的邻域内的点数是否超过阈值点数，超过则构成核⼼点·扫描数据集，寻找没有被聚类的数据点，重复第⼆步·输出划分的类，并输出异常值点（不和其他密度相连）1.5 神经⽹络的⽅法代表：SOM算法·数据集合，权重向量为，，归⼀化处理·寻找获胜的神经元，找到最⼩距离，对于每⼀个输⼊数据，找到与之最相匹配的节点令为为的距离，更新权重：·更新临近节点，，其中代表学习率1.6 基于图的聚类⽅法代表：谱聚类算法·计算邻接矩阵，度矩阵，·计算拉普拉及矩阵·计算归⼀化拉普拉斯矩阵·计算的特征值和特征向量·对Q矩阵进⾏聚类，得到聚类结果2. 聚类算法的评价指标⼀个好的聚类⽅法可以产⽣⾼品质簇，是的簇内相似度⾼，簇间相似度低。
机器学习-层次聚类（划分聚类）层次聚类（划分聚类）聚类就是对⼤量未知标注的数据集，按照数据内部存在的数据特征将数据集划分为多个不同的类别，使类别内的数据⽐较相似，类别之间的数据相似度⽐较⼩；属于⽆监督学习。
算法步骤1.初始化的k个中⼼点2.为每个样本根据距离分配类别3.更新每个类别的中⼼点（更新为该类别的所有样本的均值）4.重复上⾯两步操作，直到达到某个中⽌条件层次聚类⽅法对给定的数据集进⾏层次的分解，直到满⾜某种条件为⽌，传统的层次聚类算法主要分为两⼤类算法：凝聚的层次聚类AGNES算法==>采⽤⾃底向上的策略。
agglomerative（凝聚） nesting（嵌套）最初将每个对象作为⼀个簇，然后这些簇根据某些准则（两个簇之间的相似度度量⽅式）被⼀步⼀步合并，两个簇间的距离可以由这两个不同簇中距离最近的数据点的相似度来确定；聚类的合并过程反复进⾏直到所有的对象满⾜簇数⽬。
AGNES就是把每个⽔果当成⼀个类别，然后再进⾏聚类。
合并点的选择：两个簇间的最⼤距离（complete）两个簇间的最⼩距离（word）两个簇间的平均距离（average）适合链式的聚类，条状的就⽐较适合。
代码：linkages ：complete,word,averageimport numpy as npimport matplotlib as mplimport matplotlib.pyplot as plt# 调⽤AGNESfrom sklearn.cluster import AgglomerativeClusteringfrom sklearn.neighbors import kneighbors_graph ## KNN的K近邻计算import sklearn.datasets as ds# 拦截异常信息import warningswarnings.filterwarnings('ignore')# 设置属性防⽌中⽂乱码mpl.rcParams['font.sans-serif'] = [u'SimHei']mpl.rcParams['axes.unicode_minus'] = False# 模拟数据产⽣: 产⽣600条数据np.random.seed(0)n_clusters = 4N = 1000data1, y1 = ds.make_blobs(n_samples=N, n_features=2, centers=((-1, 1), (1, 1), (1, -1), (-1, -1)), random_state=0)n_noise = int(0.1 * N)r = np.random.rand(n_noise, 2)min1, min2 = np.min(data1, axis=0)max1, max2 = np.max(data1, axis=0)r[:, 0] = r[:, 0] * (max1 - min1) + min1r[:, 1] = r[:, 1] * (max2 - min2) + min2data1_noise = np.concatenate((data1, r), axis=0)y1_noise = np.concatenate((y1, [4] * n_noise))# 拟合⽉⽛形数据data2, y2 = ds.make_moons(n_samples=N, noise=.05)data2 = np.array(data2)n_noise = int(0.1 * N)r = np.random.rand(n_noise, 2)min1, min2 = np.min(data2, axis=0)max1, max2 = np.max(data2, axis=0)r[:, 0] = r[:, 0] * (max1 - min1) + min1r[:, 1] = r[:, 1] * (max2 - min2) + min2data2_noise = np.concatenate((data2, r), axis=0)y2_noise = np.concatenate((y2, [3] * n_noise))def expandBorder(a, b):d = (b - a) * 0.1return a - d, b + d## 画图# 给定画图的颜⾊cm = mpl.colors.ListedColormap(['#FF0000', '#00FF00', '#0000FF', '#d8e507', '#F0F0F0'])plt.figure(figsize=(14, 12), facecolor='w')linkages = ("ward", "complete", "average") # 把⼏种距离⽅法，放到list⾥，后⾯直接循环取值for index, (n_clusters, data, y) in enumerate(((4, data1, y1), (4, data1_noise, y1_noise),(2, data2, y2), (2, data2_noise, y2_noise))):# 前⾯的两个4表⽰⼏⾏⼏列，第三个参数表⽰第⼏个⼦图(从1开始，从左往右数)plt.subplot(4, 4, 4 * index + 1)plt.scatter(data[:, 0], data[:, 1], c=y, cmap=cm)plt.title(u'原始数据', fontsize=17)plt.grid(b=True, ls=':')min1, min2 = np.min(data, axis=0)max1, max2 = np.max(data, axis=0)plt.xlim(expandBorder(min1, max1))plt.ylim(expandBorder(min2, max2))# 计算类别与类别的距离(只计算最接近的七个样本的距离) -- 希望在agens算法中，在计算过程中不需要重复性的计算点与点之间的距离 connectivity = kneighbors_graph(data, n_neighbors=7, mode='distance', metric='minkowski', p=2, include_self=True)connectivity = (connectivity + connectivity.T)for i, linkage in enumerate(linkages):##进⾏建模，并传值ac = AgglomerativeClustering(n_clusters=n_clusters, affinity='euclidean',connectivity=connectivity, linkage=linkage)ac.fit(data)y = bels_plt.subplot(4, 4, i + 2 + 4 * index)plt.scatter(data[:, 0], data[:, 1], c=y, cmap=cm)plt.title(linkage, fontsize=17)plt.grid(b=True, ls=':')plt.xlim(expandBorder(min1, max1))plt.ylim(expandBorder(min2, max2))plt.tight_layout(0.5, rect=(0, 0, 1, 0.95))plt.show()AGNES使⽤不同合并⽅式的结果：分裂的层次聚类（类似于决策树）DIANA算法==>采⽤⾃顶向下的策略。
聚类算法实验1、数据集Iris Data SetIris Data Set是一个用于区分分析（discriminant analysis）的多变量数据集。
该数据集中的数据是由鸢尾属植物的三种花——Setosa、Versicolor与Virginica——的测量结果所组成，数据集中共包含150组数据信息，每一类别植物有50组数据。
每种花的特征用5种属性描述：①萼片长度sepal length（厘米）②萼片宽度sepal width（厘米）③花瓣长度petal length（厘米）④花瓣宽度petal width（厘米）⑤类——Setosa、Versicolor、Virginica在数据集的分析文件中给出了该数据集的一些统计摘要，简要内容如下：2、数据挖掘——数据预处理现实世界中数据大体上都是不完整，不一致的脏数据，无法直接进行数据挖掘，或挖掘结果差强人意。
为了提前数据挖掘的质量产生了数据预处理技术。
数据预处理有多种方法：数据清理，数据集成，数据变换，数据归约等。
这些数据处理技术在数据挖掘之前使用，大大提高了数据挖掘模式的质量，降低实际挖掘所需要的时间。
（1）数据清理首先是处理空缺值，比如：Iris Data Set中某一项数据的花瓣长度petal length项没有记录，就要对该项进行处理。
然后是处理噪声数据，通过考察周围的值来平滑存储数据的值。
最后是处理不一致数据。
对以上三种流程的主要方法是纸上记录、人工的加以更正等。
（2）数据集成即由多个数据存储合并数据。
（3）数据变换将数据转换成适用于数据挖掘的形式。
（4）数据归约数据挖掘时往往数据量非常大，在少量数据上进行挖掘分析需要很长的时间，数据归约技术可以用来得到数据集的归约表示，它小得多，但仍然接近于保持原数据的完整性，并结果与归约前结果相同或几乎相同。
具体到本实验中，由于Iris Data Set提供的信息比较完善，每个数据对象都由4维的数据和1维的类型组成，这五个数据之间用了“，”隔开没有空缺值、噪声数据等。
cure聚类中心点计算公式
（原创版）
目录
1.概述 CURE 聚类算法
2.介绍 CURE 聚类的中心点计算公式
3.总结 CURE 聚类的优点和应用场景
正文
CURE(Cluster Ensembles) 聚类算法是一种基于集成学习的聚类方法，通过结合多个聚类结果来得到最终的聚类结果。
CURE 聚类算法的主要思想是首先对数据进行多个聚类，然后对每个聚类的中心点进行投票，最终得到一个新的中心点。
这个过程会重复进行，直到满足停止条件。
在 CURE 聚类算法中，计算中心点的公式是非常重要的。
CURE 聚类的中心点计算公式如下：
中心点 = (x1 + x2 +...+ xn) / n
其中，x1, x2,..., xn 是每个聚类的中心点，n 是聚类的数量。
通过这个公式，我们可以得到 CURE 聚类的中心点，从而得到最终的聚类结果。
CURE 聚类算法具有很多优点，例如具有良好的稳定性和鲁棒性，可以处理不同形状的数据集，同时也可以处理不同密度的数据集。
因此，CURE 聚类算法在很多应用场景中都得到了广泛的应用，例如数据挖掘、图像处理和生物信息学等领域。
总的来说，CURE 聚类算法是一种非常有效的聚类方法，其中心点计算公式也非常简单易懂。
第1页共1页。
cure聚类中心点计算公式摘要：1.引言2.CURE聚类简介3.中心点计算公式4.公式解释与分析5.实例演示6.结论正文：【提纲】1.引言在数据挖掘和机器学习中，聚类算法是一种重要的分析方法。
CURE （Clustering Using Representatives Uniformly Extracted from Clusters）聚类算法是一种基于代表点的聚类方法，具有较好的聚类性能。
本文将详细介绍CURE聚类算法及其中心点计算公式。
2.CURE聚类简介CURE聚类算法是一种基于代表点的聚类方法。
它在聚类过程中，通过提取每个簇的代表点，使得代表点能够均匀地覆盖整个簇。
CURE算法具有较好的聚类性能，尤其在处理大规模数据集和高维数据时表现出较好的稳定性。
3.中心点计算公式在CURE聚类算法中，中心点的计算公式如下：中心点= ( representatives_sum / representative_count )其中，representatives_sum表示代表点的属性值之和，representative_count表示代表点的数量。
4.公式解释与分析该公式通过计算代表点的属性值之和与代表点数量的比值，得到中心点的属性值。
这样做可以保证中心点能够反映整个簇的平均属性值，同时避免受到极端值的影响。
5.实例演示以下是一个简单的实例来说明CURE聚类算法中中心点的计算过程：假设有一个包含5个数据点的簇，它们的属性值分别为（1，2），（3，4），（5，6），（7，8），（9，10）。
首先，计算代表点的属性值之和：representatives_sum = (1+3+5+7+9) * 2 + (2+4+6+8+10) * 2 = 120 接着，计算代表点的数量：representative_count = 5最后，根据公式计算中心点的属性值：中心点= 120 / 5 = (1+3+5+7+9) / 5 = 56.结论CURE聚类算法通过提取代表点并计算其中心点，实现了对数据集的有效聚类。
一篇文章透彻解读聚类分析及案例实操【数盟致力于成为最卓越的数据科学社区，聚焦于大数据、分析挖掘、数据可视化领域，业务范围：线下活动、在线课程、猎头服务、项目对接】【限时优惠福利】数据定义未来，2016年5月12日-14日DTCC2016中国数据库技术大会登陆北京！大会云集了国内外数据行业顶尖专家，设定2个主会场，24个分会场，将吸引共3000多名IT 人士参会！马上领取数盟专属购票优惠88折上折，猛戳文末“阅读原文”抢先购票！摘要：本文主要是介绍一下SAS的聚类案例，希望大家都动手做一遍，很多问题只有在亲自动手的过程中才会有发现有收获有心得。
这里重点拿常见的工具SAS+R语言+Python介绍!1 聚类分析介绍1.1 基本概念聚类就是一种寻找数据之间一种内在结构的技术。
聚类把全体数据实例组织成一些相似组，而这些相似组被称作聚类。
处于相同聚类中的数据实例彼此相同，处于不同聚类中的实例彼此不同。
聚类技术通常又被称为无监督学习，因为与监督学习不同，在聚类中那些表示数据类别的分类或者分组信息是没有的。
通过上述表述，我们可以把聚类定义为将数据集中在某些方面具有相似性的数据成员进行分类组织的过程。
因此，聚类就是一些数据实例的集合，这个集合中的元素彼此相似，但是它们都与其他聚类中的元素不同。
在聚类的相关文献中，一个数据实例有时又被称为对象，因为现实世界中的一个对象可以用数据实例来描述。
同时，它有时也被称作数据点(Data Point)，因为我们可以用r 维空间的一个点来表示数据实例，其中r 表示数据的属性个数。
下图显示了一个二维数据集聚类过程，从该图中可以清楚地看到数据聚类过程。
虽然通过目测可以十分清晰地发现隐藏在二维或者三维的数据集中的聚类，但是随着数据集维数的不断增加，就很难通过目测来观察甚至是不可能。
1.2 算法概述目前在存在大量的聚类算法，算法的选择取决于数据的类型、聚类的目的和具体应用。
大体上，主要的聚类算法分为几大类。
各种聚类算法的比较聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。
目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。
摘自数据挖掘中的聚类分析研究综述这篇论文。
1、层次聚类算法1.1聚合聚类1.1.1相似度依据距离不同：Single-Link:最近距离、Complete-Link：最远距离、Average-Link：平均距离1.1.2最具代表性算法1）CURE算法特点：固定数目有代表性的点共同代表类优点：识别形状复杂，大小不一的聚类，过滤孤立点2）ROCK算法特点：对CURE算法的改进优点：同上，并适用于类别属性的数据3）CHAMELEON算法特点：利用了动态建模技术1.2分解聚类1.3优缺点优点：适用于任意形状和任意属性的数据集；灵活控制不同层次的聚类粒度，强聚类能力缺点：大大延长了算法的执行时间，不能回溯处理2、分割聚类算法2.1基于密度的聚类2.1.1特点将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类1）DBSCAN：不断生长足够高密度的区域2）DENCLUE：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合3）OPTICS、DBCLASD、CURD：均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进2.2基于网格的聚类2.2.1特点利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成网格结构；1）优点：处理时间与数据对象的数目无关，与数据的输入顺序无关，可以处理任意类型的数据2）缺点：处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性2.2.2典型算法1）STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率2）STING+：改进STING，用于处理动态进化的空间数据3）ＣＬＩＱＵＥ：结合网格和密度聚类的思想，能处理大规模高维度数据4）WaveCluster：以信号处理思想为基础2.3基于图论的聚类2.3.1特点转换为组合优化问题，并利用图论和相关启发式算法来解决，构造数据集的最小生成数，再逐步删除最长边1）优点：不需要进行相似度的计算2.3.2两个主要的应用形式1）基于超图的划分2）基于光谱的图划分2.4基于平方误差的迭代重分配聚类2.4.1思想逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解1）概率聚类算法期望最大化、能够处理异构数据、能够处理具有复杂结构的记录、能够连续处理成批的数据、具有在线处理能力、产生的聚类结果易于解释2）最近邻聚类算法——共享最近邻算法SNN特点：结合基于密度方法和ROCK思想，保留K最近邻简化相似矩阵和个数不足：时间复杂度提高到了O(N^2)3）K-Medioids算法特点：用类中的某个点来代表该聚类优点：能处理任意类型的属性；对异常数据不敏感4）K-Means算法1》特点：聚类中心用各类别中所有数据的平均值表示2》原始K-Means算法的缺陷：结果好坏依赖于对初始聚类中心的选择、容易陷入局部最优解、对K值的选择没有准则可依循、对异常数据较为敏感、只能处理数值属性的数据、聚类结构可能不平衡3》K-Means的变体Bradley和Fayyad等：降低对中心的依赖，能适用于大规模数据集Dhillon等：调整迭代过程中重新计算中心方法，提高性能Zhang等：权值软分配调整迭代优化过程Sarafis：将遗传算法应用于目标函数构建中Berkh in等：应用扩展到了分布式聚类还有：采用图论的划分思想，平衡聚类结果，将原始算法中的目标函数对应于一个各向同性的高斯混合模型5）优缺点优点：应用最为广泛；收敛速度快；能扩展以用于大规模的数据集缺点：倾向于识别凸形分布、大小相近、密度相近的聚类；中心选择和噪声聚类对结果影响大3、基于约束的聚类算法3.1约束对个体对象的约束、对聚类参数的约束；均来自相关领域的经验知识3.2重要应用对存在障碍数据的二维空间按数据进行聚类,如COD(Clustering with Obstructed Distance)：用两点之间的障碍距离取代了一般的欧式距离3.3不足通常只能处理特定应用领域中的特定需求4、用于高维数据的聚类算法4.1困难来源因素1）无关属性的出现使数据失去了聚类的趋势2)区分界限变得模糊4.2解决方法1)对原始数据降维2)子空间聚类CACTUS：对原始空间在二维平面上的投影CLIQUE：结合基于密度和网格的聚类思想，借鉴Apriori算法3)联合聚类技术特点：对数据点和属性同时进行聚类文本：基于双向划分图及其最小分割的代数学方法4.3不足：不可避免地带来了原始数据信息的损失和聚类准确性的降低5、机器学习中的聚类算法5.1两个方法1)人工神经网络方法自组织映射：向量化方法，递增逐一处理；映射至二维平面，实现可视化基于投影自适应谐振理论的人工神经网络聚类2)基于进化理论的方法缺陷：依赖于一些经验参数的选取，并具有较高的计算复杂度模拟退火：微扰因子；遗传算法（选择、交叉、变异）5.2优缺点优点：利用相应的启发式算法获得较高质量的聚类结果缺点：计算复杂度较高，结果依赖于对某些经验参数的选择。
基于ADS-B数据挖掘的4D航迹预测方法马兰;高永胜【摘要】针对空中交通管制中航空器轨迹预测误差较大的问题,提出了一种基于ADS-B数据挖掘的航迹预测方法.该方法通过对ADS-B历史飞行数据深入挖掘,对航线、机型等数据进行统计分析、滤波降噪处理再进行CURE聚类分析.以青岛—北京CDG4651航班航迹数据为依据,预测某日的航迹轨迹、过点时间及过点高度等,结果表明,该预测方法具有准确性和实用性.【期刊名称】《中国民航大学学报》【年(卷),期】2019(037)004【总页数】4页(P1-4)【关键词】航迹预测;数据挖掘;ADS-B;4D轨迹预测;CURE聚类【作者】马兰;高永胜【作者单位】中国民航大学空中交通管理学院,天津300300;中国民航大学空中交通管理学院,天津300300【正文语种】中文【中图分类】V355;TP3914D 航迹是航空器在时空上的运行轨迹，包含其所在位置的经度、纬度、高度的三维坐标在时间轴上的变化。
新一代空中交通管理系统通过各空域流量的匹配和优化、冲突探测与解脱技术，航班排序和调度手段等来辅助空管人员进行决策，均离不开对航迹的精确预测。
航空器的4D 航迹预测即推算航空器在将来一段时间内飞行的4D 轨迹，主要为了维持航空器有序运行、保证空中交通系统安全和提高空域流量等。
鉴于4D 航迹预测在空中交通运输系统的重要性和迫切性，国内外学者对此研究进行以下尝试：文献[1-2]基于雷达数据建立的运动学模型预测4D 航迹，解决了其他预测模型参数过多的问题；文献[3]提出了基于隐马尔科夫模型的自适应参数选择轨迹预测模型，并在给定的航迹数据参数中选出最优的预测模型；文献[4-5]根据基本飞行模型进行航迹研究，仅得出航迹特征点和到达航迹特征点的时间；文献[6-8]重点针对终端区4D 轨迹来控制和优化飞机的程序轨迹，从爬升段和进近段设计航空器飞行程序进行预测；文献[9]在等角飞行航迹的基础上，运用卡尔曼滤波（KF）和扩展卡尔曼滤波（EKF）联合算法确定航空器的地速，以此推断航空器过点时间，此方法对于短期航迹预测效果较佳。
CURE聚类算法的实现任务背景聚类（clustering）就是将数据对象分组成为多个类或簇（cluster），在同一簇中的对象之间具有较高的相似度，而不同的簇中对象差别较大。
相异度是根据描述对象的属性值来计算的。
距离是经常采用的度量方式。
聚类分析源于许多研究领域，包括数据挖掘，统计学，生物学，以及机器学习。
作为统计学的一个分支，聚类分析已经被广泛的研究了许多年，主要集中在基于距离的聚类分析。
基于k-means（k-平均值），k-medoids（k-中心点）和其他一些方法的聚类分析工具已经被加入到许多统计分析软件包或系统中，例如S-Plus，SPSS，以及SAS。
CURE（Clustering Using Representatives）是一种针对大型数据库的高效的聚类算法。
基于划分的传统的聚类算法得到的是球状的，相等大小的聚类，对异常数据比较脆弱。
CURE采用了用多个点代表一个簇的方法，可以较好的处理以上问题。
并且在处理大数据量的时候采用了随机取样，分区的方法，来提高其效率，使得其可以高效的处理大量数据。
基本目标聚类算法CURE的算法实现。
对图形进行聚类，在时间，结果方面对其性能进行评估。
算法流程CURE的算法在开始时，每个点都是一个簇，然后将距离最近的簇结合，一直到簇的个数为要求的K。
它是一种分裂的层次聚类。
算法分为以下6步：1）从源数据对象中抽取一个随机样本S。
2）将样本S分割为一组划分。
3）对划分局部的聚类。
4）通过随机取样提出孤立点。
如果一个簇增长得太慢，就去掉它。
5）对局部的簇进行聚类。
6）用相应的簇标签标记数据。
算法设计(1)基本聚类算法procedure cluster(S, k) /*将数据集S聚类成为k个簇*/begin1. T := build_kd_tree(S) /*对应数据集S建立一个K-DTree T*/2. Q := build_heap(S) /*对应数据集S建立一个堆Q*/3. while size(Q) > k do { /*聚类直至簇的个数为k */4. u := extract_min(Q) /*找到最近的两个簇u，v */5. v := u.cloest6. delete(Q, v)7. w := merge(u, v) /*将u，v合并为簇w */8. delete_rep(T, u);delete_rep(T, v);insert_rep(T, w)9. w.cloest := x /* x is an arbitrary cluster in Q*/10. for each x∈Q do{ /*调节因合并带来的T和Q的变化*/11. if (dist(w,x) < dist(w,w.cloest))12. w.cloest := x13. if x.cloest is either u or v {14. if dist(x, x.cloest) < dist(x.w)15. x.cloest := cloest_cluster(T, x, dist(x,w))16. else17. x.cloest := w18. relocate(Q, x)19. }20. else if dist(x, x.cloest) > dist(x, w) {21. x.cloest := w22. relocate(Q, x)23. }24. }25. insert(Q, w)26. }end此程序段用到的数据结构有Heap，和K-DTree。
为了合并距离最短的两个聚类，需要构建一个K-DTree来找到空间中的一聚类最近的一个聚类，之后把K-DTree 中的聚类按照其与最近的聚类的距离进行排序（用的是堆排序），找到最近的两个的聚类，将它们合并（对应函数merge（））。
(2)Merge算法procedure merge(u, v) /*合并两个簇，并确定新簇的中心点和代表点*/ begin1. w := u ∪v2. w.mean :=/*求新簇w的中心点*/3. tmpSet := Ø /*用来存c个代表点的集合*/4. for i := 1 to c do { /*选出c个代表点*/5. maxDist := 0 /*距中心点或代表点最远的点作为代表点*/6. foreach point p in cluster w do {7. if i = 18. minDist := dist( p, w.mean )9. else10. minDist := min{ dist( p, q ) : q ∈tmpSet }11. if( minDist >= maxDist ) {12. maxDist := minDist13. maxPoint := p14. }15. }16. tmpSet := tmpSet ∪{ maxPoint }17. }18. foreach point p in tmpSet do /*按照收缩因子α处理代表点*/19. w.rep := w.rep ∪{ p + α*( w.mean – p )}20. return wend此程序段同时描述了如何选取代表点：对每个簇选择c个分布较好的点，通过系数α向中心收缩，其中0 <α<1。
α小，收缩小，可以区分拉长的簇；α大，靠近中心点，得到的簇更紧凑。
显然，如果α=1，聚类w的代表点就是w.mean，即其中心点，此时类似于Centroid-base approach，即中心点代表簇，当α=0，此时类似于All-points approach，即所有点代表簇。
簇之间的距离定义为：两个簇的代表点之间的最小距离，即：点到簇的距离与此类似，是该点到最近的簇的代表点的距离。
c个代表点体现了簇的物理几何形状；向中心收缩可以降低异常点的影响。
两个簇组合后的新簇，则重新选择c个点作为簇的代表。
(3)数据取样:在对大规模数据库进行聚类分析时，数据取样是一种常用的提高聚类效率的方法，即对整个数据库进行数据取样，然后对取样数据库进行聚类分析，而对未被取样的数据进行聚类标注。
这样，对大规模数据库的聚类分析就转化为对较小规模的取样数据库的聚类分析。
由于没有考虑到整个数据库的数据，聚类质量必然会受到影响。
但是，只要取样均匀且取样率适当，则取样数据库也可以较好地反映整个数据库状况，从而在保证聚类质量的同时提高聚类效率。
定理1：对一个簇u，如果取样大小s满足：那么，样本中属于簇u的点的个数小于f|u|的概率小于δ，0<=δ<=1因此，采用chernoff bounds来确定的最小的取样数据量：这就表示着如果我们只关心数据点数目大于的聚类，且最小的聚类至少有ξ个数据点，那么我们只需要一个独立于原始数据点个数的取样数目。
(4)分区方法分区过程如下：将所有样本分成p个分区，每个分区大小n/p。
每个分区内作聚类，直到分区内的簇的个数为n/pq, q > 1。
或者指定一个距离阈值，当最近簇距离大于阈值，则停止。
在CURE算法中，First pass 每个分区：Second pass 总聚类:p,q的最好选值：使n/pq为k的2~3倍。
其优点是：减少执行时间；减少输入数据，保证可以在内存中存放所有聚类的代表点。
(5)标记数据所属的簇因为CURE用c个点来代表一个聚类，因此在聚类完成后，对未参加聚类的数据或新增的数据进行标注从而计算聚类的可信度时，其可以准确的识别非球状数据集，使得标注更加准确。
(6)异常点的处理1．随机取样，过滤了大多数的异常点；2．异常点所在的簇的点个数少于正常簇的点的个数，此时分两个阶段消除异常点。
a. 第一阶段：增长速度慢的簇作为异常，以点的个数作为阈值。
Fraction（簇的个数为初始簇个数的比例；比如：1/3）的取值很重要；当簇的个数减少到fraction 时，开始作消除异常点的操作。
b. 第二阶段：在第一阶段中，可能有些相近的异常点已经组合，所以进行第二阶段中异常点形成的簇非常小，很容易鉴别。
数据取样算法:在对大规模数据库进行聚类分析时，数据取样是一种常用的提高聚类效率的方法，即对整个数据库进行数据取样，然后对取样数据库进行聚类分析，而对未被取样的数据进行聚类标注。
这样，对大规模数据库的聚类分析就转化为对较小规模的取样数据库的聚类分析。
由于没有考虑到整个数据库的数据，聚类质量必然会受到影响。
但是，只要取样均匀且取样率适当，则取样数据库也可以较好地反映整个数据库状况，从而在保证聚类质量的同时提高聚类效率。
与以前的基于取样的聚类算法相比。
取样算法：这种算法只需扫描一遍被取样数据库，而且使用恒定的内存空间，便可以从N个记录中随机取出n个取样记录。
其基本思想是:从第N-n+1条记录开始，做下列操作。
设当前处理的是第t个记录(n+1≤t≤N)，u是产生的一个随机数(u∈〔0，t-1〕)，若u<n，则把第u个记录替换成第t个记录。
可以证明该算法能够得到均匀的取样结果。
确定取样率很重要。
为保证聚类质量，取样数据库应该能够有效地代表原数据库。
若取样率太低，取样数据库必然会丢失原数据库的某些特质，导致聚类效果失真。
测试方法：对图形（事实上相当于2维的数据库数据）进行聚类。
输入：左图输出：类似右图，即把两组点分开，可以用颜色的不同来表示一个图形约有几万个点，取样数目在k*500至k*1000（k为分组的数目），左右，可以自己掌握。
