传统与流数据聚类算法

刘晓璐，王志栋，单广荣

（1.西北民族大学，甘肃省民族语言智能处理重点实验室，兰州 730030；2.大连交通大学机车车辆工程学院，大连 116028）

0 引言

数据流挖掘是指从大量连续生成的数据中发现知识的过程[8]。数据流挖掘过程多数采用聚类算法。聚类，是将一个数据集对象进行分类的过程，在这个过程中，我们通过对比一些性能将相似的对象进行分类。如在市场分析中，从客户大数据库中划分客户群，需要根据不同客户的不同需求等特征进行客户群划分[4-5]；其次在生物学动植物分类中，通过基因的分类来认识种群中的固有结构等都是聚类的典型应用，都需要聚类算法聚类进行特征提取[6-9]。因此本文针对一些传统聚类算法以及流数据聚类算法进行分析和总结。

1 聚类概述

聚类在进行分类时不依赖预先定义的类以及一些标记，而是根据相似度进行分类。一些未被处理的数据作为输入数据进行聚类任务处理，处理结果希望在类之间的相似度尽可能地低，类内相似度尽量地高。例如将聚类运用到股票系统中，投资者和股民可以利用聚类后的结果进行预判，选择合适的股票，如将一些相似波动情况的股票划为一类，并按照其不同的特征再进行分类，方便股民参考。聚类不仅可以用于样本分类，还可以用于网络欺诈风险预估等[9]。

聚类在进行数据挖掘时，必须具备以下的特点：

（1）可伸缩性：有处理不同大小数据集的能力。

（3）发现任意形状的聚类：既要能处理凸型簇也要能处理非凸型簇。

（4）输入参数：许多算法中需要人为输入参数，参数输入不当会给聚类造成很大影响。

（5）对有损数据的处理：原始数据中会出现有损数据，需要进行有效处理，保证聚类质量[10]。

（6）对数据输入顺序不敏感：对某些算法当输入顺序改变时，算法效果会产生相应的变化，不利于最终结果[11]。

（7）高维性：数据具有高维性。

（8）基于约束的聚类：找到事物的主要属性进行聚类。

2 聚类算法

在本文中，主要介绍传统聚类算法[12]以及流数据聚类算法[13-14]，在介绍时，将会选取该种类的几个算法进行大致介绍以了解不同类型的聚类算法。下面将介绍基于划分、基于层次、基于密度和基于网格的传统与流数据聚类算法。

2.1 基于划分的聚类算法

基于划分的传统聚类算法，就是将数据集进行分组的过程，其中一组只包含一个对象，一个对象只属于一个组[15]。K-means 算法[16-17]的基本思想是：确定 k 个簇中心，按照距离分配其他样本点，直至全部分配完成后重新确定簇心，再次分配，即不断重复此过程，直到簇心不变化或者样本点不变化为止[16]。K-means 算法适用于簇状为凸的数据，处理效率高；但是，此算法对异常数据较为敏感并且需要人为指定簇数目，仅仅试用于簇状为凸面数据，限制聚类属性，使用范围较小，常常终止于局部最优。因此，基于K-means 算法提出了二分K-means，使算法终止于全局最优[17]。并且为了改善K-means 算法对聚类属性限制的缺点，提出了K-medoids[18-19]。该算法第一步与K-means 算法相同，先随机确定k 个中心点，之后通过其他样本点与该中心点距离进行样本点分配，全部分配完成后不断通过非中心点替代中心点，提高最终聚类结果。K-中心点算法相较于K-means 算法而言没有对聚类属性的限制，且对噪声、异常数据不敏感，但是该算法较为耗时，也需要事先指定簇中心数目。

模型(3)仍为非线性规划模型，与模型(1)和(2)最大的区别在于不再是基于设备的可利用生产时间来构成约束条件，而是基于设备的可用数量来构成约束条件，以此反映出从生产设备的数量方面进行最优分配和调度．

流数据聚类STREAM 算法基于K-means 算法提出，用于处理数据流。该算法每次只处理m 个数据，对m 个数据进行聚类形成k 个簇，此时仅保留簇中心而丢弃其余数据，其中k 个簇中心会通过权值来记录每个簇中的数据点的个数。随着数据流的进入，STREAM算法仍保持每次处理m 个数据。STREAM 算法与传统的聚类算法如BIRCH 相比，能产生质量更高的聚类结果。由于其没有对数据流变化以及时间进行考虑，导致不能及时更新近期数据流对聚类结果的影响以及不能展现不同时间粒度产生的不同聚类结果[16]。

2.2 基于层次的聚类算法

层次法基本原理是将每一个样本点视为一个类，按距离进行聚类，对形成的类再次按距离进行聚类，不断重复此过程直到只有一个大类为止[20]。

BIRCH 算法中包含两步，首先是构建聚类特征树，聚类特征树中包含了数据对象的所有属性；得到特征树后通过其他算法对其进行聚类[21]。BIRCH 有以下的优缺点，首先该算法只需要存储节点和地址，对于数据本身不需要存储，因此节约存储空间[22]；其次由于该算法在构建特征树时只需要依次扫描，因此速度较快[23]。该算法还可以识别噪声点，完成数据预处理。但是该算法也存在一些缺点，首先BIRCH 算法在特征树上可以存储的特征有限，会导致聚类结果不准确，因此该算法不适合于高维数据聚类；其次当数据的簇状不是凸面时，聚类效果也不好。因此，基于上述缺点提出CURE 算法[24]改善其缺点，使其可以更好地处理大数据且识别噪声能力强。

基于层次的流数据聚类CluStream 算法[25]，该算法能够完全适应数据流快速到达的特点并且能够挖掘出数据流的潜在演化特征，产生球形的聚类结果；由于其对于噪声数据敏感，每当出现异常数据时算法将会出现不稳定性；随着噪声数据增加，微簇数量也会增加，该算法限制微簇数量，由此必须进行合并删减，降低了算法聚类结果的准确度。

2.3 基于密度的聚类算法

基于密度的聚类算法整体思想是基于密集数据点进行处理，数据空间中的每一簇都是由很多密集数据点组成，并被稀疏区域划分，通过从稀疏区域中找到密集数据点，并将稀疏区域视为噪声点，从而进行数据集的处理。

DBSCAN 算法[26-27]寻找密集数据点过程是：首先需要随机确定一个点，找出与此点距离小于等于扫描半径的所有附近点，若所有附近点的数量大于等于最小包含点数，则将此点与其找出的所有点形成一个簇，并将此点标记为已访问的点。按照上述过程递归访问所有的未被标记的点，从而不断扩展簇。DBSCAN 算法可以发现任意形状的簇，并且在使用聚类算法时不需要指定最终形成的簇值k[25]，其次该算法不会受到噪声点的干扰，可以摆脱噪声点的干扰。该算法面对高维数据时效果不是很好，在样本数据分布不均匀的情况下，聚类质量都会相应降低。

基于密度的流数据聚类DenStream 算法[13]，主要思想是基于CluStream 算法的联机、脱机结构加入潜在微簇（p-micro-cluster）和孤立点微簇（o-micro-cluster）两种结构，通过簇密度与阈值的比较区分两种微簇结构，若其密度小于给定阈值，则说明是孤立点微簇。算法开始时，进行数据合并，首先尝试合并至潜在微簇中，若不成功，则合并在微簇结构中。若成功，则进行微簇类型的转换，只有簇密度大于阈值，才能将孤立点微簇转化为潜在微簇。若合并失败，则建立孤立点微簇以存储此数据。在脱机部分，则直接使用DBSCAN 算法对两类微簇进处理，得到聚类结果。DenStream 算法通过两种微簇结构可以进行边缘数据和真实数据的区分，成为了现在基于流数据聚类算法的主流方法。但是由于合并失败时创建的微簇数量不断增加将会导致所占内存较大，并且在判断并移除边缘值时计算量较大。

2.4 基于网格的聚类算法

CLIQUE 算法在给定分布情况不均衡的大数据集中，进行稀疏、密集区域的区分，将区分后相连的密集区域作为簇，由此完成聚类过程。其中稀疏区域和密集区域区分通过其内数据点是否超过给定模型参数来决定，若数据点个数超过此参数，则这个区域就是密集区域。因此，CLIQUE 算法对处理大数据集具有高效性并且对异常数据不敏感，另外，当数据输入顺序改变时，聚类结果不会受到影响。

基于网格流数据聚类D-Stream 算法，此算法整个聚类过程与密度息息相关，该算法在聚类过程中也分为两个部分，即联机部分和脱机部分，联机部分是将流数据映射到网格中，脱机部分根据密度进行聚类，在第一个时间隙后，脱机部分根据网格密度形成第一个初始簇，之后在每个时间隙后对当前簇进行调整。DStream 算法在聚类过程中不依赖于查询，每一个单元中都有对应的信息汇总，因此其效率较高，速度快并且不限制数据形状，运用范围广。其缺点是网格质量决定聚类质量，当网格粒度小，较为精细，这样产生的聚类效果也好，同样的聚类花费代价大；相同而言，当网格粒度大时，对应的聚类效果也会降低。并且此算法只考虑了网格水平垂直方面的关系，没有考虑到与其他相邻单元的关系，也会造成聚类质量的降低。

3 结语

聚类研究工作一直以来在图像处理、人工智能、数据挖掘领域都受到高度重视，现有的聚类算法都存在一些缺陷，不能满足现实应用，因此聚类算法研究从未停止，很多研究工作都希望能够提出新算法进行使用。如本文前面所述，无论是基于划分的K-means 算法还是基于层次的CURE 算法都需要事先指定簇数目进行聚类，但是我们发现，在实际应用以及实验中，簇数目是未知的，需要根据实验过程而确定，因此针对此方面的缺陷依旧需要不断研究。再者来说，我们已有的任何聚类算法都是针对某种情况而言，没有一种算法适用于任何情况，因此，此方面也是聚类研究的热点问题。大数据时代，需要处理的数据量及其庞大，而目前的一些算法仅仅适用于小规模数据和低维数据，因此，既能够处理大规模数据而且处理速度快，效率高的聚类算法对现有应用是及其迫切的。目前很多聚类算法仍处于理论阶段，我们在进行实验时需要假设某些条件，在实际应用方面仍然需要进一步提高。