陈向东

摘要：数据挖掘是从海量的数据中，发现隐藏的、潜在的数据规则和模式的过程；聚类算法是数据挖掘的一个重要研究方法，它按照一定的要求和规律将事物进行分类的一种数学方法。本文针对几种常用聚类算法，研究比较了几种聚类算法的聚类划分方法，探讨了几种常用聚类算法的优缺点。

关键词：数据挖掘；聚类划分；聚类

中图分类号：TP393 文献标识码：A 文章编号：1007-9416（2017）04-0151-02

随着网络应用于各个领域，随之也产生了海量的网络数据，并且这些数据是杂乱的，无规则的。对于信息数据的爆炸式的增长，而如何分析处理这些收集到的海量数据，是数据挖掘面临的首要问题。数据挖掘（Data Mining），即是从大量的、不规则的、有噪声的、模糊的数据中，提取隐藏在其中的、人们事先不知道的、但又潜在有用的信息和知识的过程[1]。聚类分析是数据挖掘领域中研究的一项重要课题，对于收集到的海量数据，通过聚类分析，发现相似数据间的知识特征，不相似数据间的数据属性之前存在较大差异，并以此规则进行数据分类，分类后的同类的数据对象之间的有一定的相似度，不同类的数据对象之间的相似度较小，每一组数据都是相似对象的集合，通过分析可以获得同类数据对象的数学模型和数据特征。

1 聚类

聚类是一个将数据划分为若干簇或类的过程，它将物理的或抽象的数据的集合分组成多个簇或类，每个簇或类中的数据特征有较高的相似性，不同的类或簇中的数据特征则不相似，这一分类过程就是聚类的过程。聚类分析就是从给定的数据集中找出同类数据对象之间的联系，被分为同一类的数据对象，由于数据特征相同，常常被当作一个对象来进行分析处理，通过对不同数据集之间的分析，挖掘出潜在的，有用的数据知识模型，为用户提供决策。对于聚类算法，很难有明确的分类标准，这些聚类方法一般具有某些类别特征。

2 聚类算法的分类

2.1 基于划分的聚类算法

假定数据集包含n个数据对象或数据元组，要将数据集通过聚类划分成K（K≤n）个簇或类，划分的簇或类要满足下列三个条件：（1）每个簇或类中包含r（r≥1）个数据对象或元组；（2）任意一个数据对象或元组只能属于一个簇或类；（3）簇或类的划分准则是：在同一个簇或类中的数据元组特征是相似的，不同簇或类中的数据元组特征是不相似的。

基于划分的聚类算法，依据初始数据集划分数目K，构建一个初始聚类划分，然后利用迭代重定位技术，将每个数据元组在各个聚类簇中进行划分，原则是：同一个划分簇中的对象或元组数据特征相似，不同划分簇中的对象或元组数据特征有较大的差异，通过迭代重定位，把数据集N最终划分成了K个簇[2]。典型的基于划分的算法有：K均值聚类和K中心点聚类。

2.2 层次方法

层次聚类算法是将数据对象组成一棵聚类树，根据层次分解的方法，对数据集进行层次分解，直到满足某种条件为止[3]。层次聚类方法有两种，一种是自底向上的合并方法，一种是自顶向下的分裂方法。层次聚类的方法的劣势在于：一旦決定采用具体的分裂法或合并方法后，如果中途发现此种方法并不合适，则无法返回更正。常见的层次聚类方法有：BIRCH（利用层次方法的平衡迭代归约聚类算法）、CHAMELEON（动态建模的层次聚类算法）。

2.3 基于密度的方法

基于密度的聚类划分：给定密度阈值，如果某个区域中数据点的密度大于密度阈值，则数据点属于相近的划分聚类，这种划分方法将数据集看作是数据空间中被低密度区域分割开的大密度区域。基于密度划分的方法代表性的算法有：DBSCAN（基于高密度连通区域的聚类算法）、DENCLUE（基于密度分布函数的聚类算法）。

2.4 基于网格的方法

基于网格的聚类划分方法是将数据对象空间分为若干个网格单元，聚类的过程就是对这些网格处理的过程，基于网格的聚类划分的优点是处理速度快，处理速度受限于量化空间中每一维的单元数目，而于网格单元数目无关。基于网格划分方法的典型算法有STING（统计信息网格聚类算法）和WaveCluster（小波变换聚类算法）。

2.5 基于模型的方法

基于模型的聚类方法有个假定前提：每个聚类划分都可以构建一个数学模型，聚类就是找到每个聚类簇相对应的数据模型的过程。数据集潜在的假定符合一系列的概率分布，数学模型算法可能数据点在空间中的分布密度函数或其它。常用的有EM（期望最大化聚类算法）。

3 几种常用的聚类算法

3.1 K-means划分聚类算法

通常给定包含N个数据对象的数据集D，将数据集按目标度量函数划分成K个簇。K-means聚类算法，是采用距离作为聚类的标准，距离越近，认为其相似度越高，聚类过程如下：

（1）随机从数据集D中选取K个数据对象作为初始点，初始化K个聚类；

（2）对于余下的每个数据元组，计算它与K个划分类中心的距离，将其归入距离最近的划分类中；

（3）更新类并重新计算K个类的中心点；

（4）repeat②，until所有聚类中心点不发生变化，此时对于每一个数据对象，都被分为唯一的一个聚类中。

K-means聚类算法需要用户给定K个聚类数，并选取K个数据点作为初始聚类中心，如若初始聚类中心选择不当，就会造成聚类结果有较大偏差；K-means聚类算法迭代的目标函数，随机选择的初始中心点，可能会导致聚类结果稳定性不够，与最优聚类有偏差。

3.2 最近邻层次聚类算法

层次聚类算法有凝聚层次聚类算法和分裂层次聚类算法；凝聚层次聚类算法，是把数据集合S（包含n个数据对象）划分成K个子集C1，C2，，…，Ck，每个子集中包含中的数据具有一定的相似性，两个子集间通常用欧几里德最小距离度量，如子集ci与子集cj距离为d（ci，cj），其中

其中是把n个数据记录看成m维空间中的n个对象向量，一般要求：

（1），对一切i，j；当=0时；

（2），对一切i，j；

（3），对一切i，j，k三角不等式成立。

最近邻层次聚类算法过程：

Step 1：将n个数据对象各自为一个类，即c1，c2，…，cn，其中ci，cj，（i，j≤n）的距离为d（ci，cj）；

Step 2：找出dmin（ci，cj），合并ci，cj为同一个类，n=n-1；

Step 3：重新计算各类间的距离d（ci，cj）；

Step 4：repeat step2，step3，Until n=1聚类结束。

层次聚类的方法简单，但是对处理离散点和噪声数据敏感，如果处理过程选择不当可能导致低质量的聚类结果，而且层次聚类算法的可伸缩性比较差。

3.3 DBSCAN一种基于高密度连通区域的聚类算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）

也是一种基于密度的聚类算法，该算法将高于一定密度的区域数据划分为一类，且在有噪声的数据集中发现任意形状的划分，一个聚类定义为密度相连的数据的最大集合。DBSCAN算法有以下定义：

（1）对象R的邻域为给定对象半径R内的邻域；

（2）S对象的R邻域至少有最小数目MinPts个对象，则称S对象为核心对象；

（3）对于数据对象集合D，如果Q是一个核心对象，且P在Q的R邻域内，则对象P从对象Q密度可达；

（4）密度可达：对于样本集合D，给定一串样本点p1，p2，…，pn，p=p1，q= pn，假如对象pi从pi-1直接密度可达，那么对象q从对象p密度可达。

（5）数据集D中存在对象S，且关于r和MinPts，对象p从对象S密度可达，对象Q从对象S也密度可达，那么对象p到对象q是关于r和MinPts密度相连。

与K-means算法相比，DBSCAN可以发现任意形状的簇类，也无需事先知道数据形成簇类的数量，并且可以识别出数据噪声点；但是对于边界样本数据的归类会有所不同，不能很好地反映数据集变化的密度；由于DBSCAN算法不对聚类数据进行预处理，所以当要处理的数据量比较大时，所耗费资源也非常大。

4 结语

本文介绍了数据挖掘中聚类算法的几种分类，然后详细分析了目前常用的3个聚类算法，并比较了各自的优缺点。聚类分析是数据挖掘中一种重要的分析数据的方法，通过分析可以看出不同分类的聚类算法各有各的优劣势，实际使用过程中可以根据实际数据情况来选择合适的聚类分析算法。由于聚类分析在电子商务、市场分析、生物学等越来越多的领域中得到了广泛应用，并且数据挖掘在实际应用中取得了巨大的商业价值，可对其进行深入研究。

參考文献

[1]丁金凤.基于网格与密度的数据流聚类算法研究[D].哈尔滨：哈尔滨工程大学，2010.

[2]王鑫.数据挖掘中聚类分析算法的研究[D].济南：山东师范大学大学，2006.

[3]范明，孟小峰.数据挖掘概念与技术[M].北京：机械工业出版社，2011：251-278.