基于密度和对象方向聚类算法的改进

1、基于密度和对象方向聚类算法的改进孟海东张玉英（内蒙古科技大学网络中心，包头）摘要针对算法所存在的问题进行了深入的研究，提出了基于密度和聚类对象方向的改进算法（算法）。该算法采取聚类对象分布密度方法来确定初始聚类中心，然后根据对象的聚类方向来发现任意形状的簇。理论分析与实空间复杂度的情况下能取得更好的聚类结果。验结果表明，改进算法在不改变时间、关键词数据挖掘聚类算法算法文献标识码中图分类号文章编号（）（，）：（），：，引言聚类分析是一种无指导机器学习方法，基于“物以类聚”的可扩展的，并且具有较高的效率。算法所存在的问题是：（）算法要求用户事先给出（要生成的簇的数目），这在某些应用中是不实际的。如

2、果用户不具备专门的领域知识，这个值的选定是非常困难的。（）有效初始聚类中心点的选取也是相当困难的，因为在该算法中是随机的选取任意个点作为初始聚类中心，选取的点不同，聚类结果可能就不同，所以算法的聚类结果对初值的依赖是很强目前，选择初始点的的，这样的依赖性导致聚类结果的不稳定。问题还没有一个简单、普遍适用的解决办法。（）目标函数采用平方误差函数，为了得到较好的聚类结果就要尽量使目标函数最小化。单一的度量方法不适合于发现任意形状的簇，而只能发现球形或差别很小的簇。（）算法采用簇的质心来代表一原理，将数据对象分组成多个类或簇，使同一个簇中的对象之间具有较高的相似度，而不同簇中的对象之间具有较高的相异

3、度。聚类算法已广泛应用在模式识别、图像处理、过程优化、配方设计等许多领域中，并取得了良好效果，受到了人们广泛重视。根据对象间相似性度量和聚类评价准则的不同，常用的聚类方法大致包括：划分方法、层次的方法、基于密度的方法、基于网格的方法和基于模型的方法等。是一种基于划分的聚类算法，因为它有理论上可靠、算法简单、速度快等优点而被广泛使用。算法分析输入：个对象的数据库，期望得到簇的数目。输出：使得平方误差准则函数最小化的个簇。（）选择个对象作为初始的簇的质心（）（）计算对象与各个簇的质心的距离，将对象划分到距离其最近个簇，质心是簇中其他对象的参照点，因此算法对“噪声”和孤立点数据是敏感的。基于密度和对

4、象方向的改进算法针对算法中存在的问题，本文提出了一种基于密度和对象方向的改进算法（的簇（）重新计算每个新簇的均值（）簇的质心不再变化，），简称算法。该算法包括四个基本步骤：（）计算对象间的相异度，形成相异度矩阵；（）计算聚类对象的密度。选取密度最大的对象作为初始聚类中心，将其邻域内的所有聚类对象形成一个簇，然后在数据集中删除这些点；通过以上算法描述可以看出，这个算法尝试找出使平方误差函数值最小的个划分。当结果簇是密集的，而簇与簇之间区别明显时，它的效果很好。对于处理大数据集，该算法是相对基金项目：内蒙古自治区高等教育科学研究项目（编号：）作者简介：孟海东（），男，博士，教授，主要研究方向：网络

5、技术、数据挖掘。张玉英（），女，硕士研究生，主要研究方向：数据挖掘。（）重复（），直到聚为个簇；（）将数据集中的剩余对象，如果它与其他对象之间的最小距离小于半径，则根据对象的方向赋给合适的簇，反之则视为“噪声”或孤立点数据。邻域半径和密度参数的选择密度参数和邻域半径的取值因实验数据不同而不同，。的选取会影响密度函数的计算，从而影响聚类初始中心点的选取；取值越小，聚类效果越好，但是数据集中的剩余对象就越多，算法的计算量增加、执行效率就会越低，并且可能使一个簇分成二个或更多个簇。执行取值越大，算法的计算量越少、效率越高，但可能使初始聚类中心点偏离密集区域，得到不符合实际对象分布的聚类中心点。从上述

6、分析可以看出，密度参数的取值在到之间，根据具体情况选取。经验取值为时效果较好。邻域半径的大小应介于所有对象间距离的最小值与最大值之间，即概念定义聚类对象的密度：已知空间中包含个对象的数据集，其中，对象的密度记作（），即：（）"（，）"采用高斯函数来计算密度，其中为密度参数。定义聚类对象的邻域：对于空间中任意对象和距离（）（），半径的取值要尽可能反应实际对象空间分布情况。根据对象数目和对象分布的密集程度可以动态地确定邻域半径的大小。邻域半径用下面的公式计算：（）其中，（）表示所有对象间距离的平均值，是对象数目，是邻域半径调节系数，；经验表明，以为中心，半径为的圆形区域，我们称

7、该区域为对象的邻域，记为（，），其中（，）表示对象与对象之间的距离。定义聚类对象的方向：根据聚类定义，可以得出对于簇边界上的对象的一个特征，即簇边界上的对象在某个方向（通常是往簇中心的方向）上有较多的临近点，而在相反方向却只有很少的临近点。由此我们得出对象方向的定义：在数据集合中，存在（，）（）（为距离），如果，则，即对象聚往簇中心的方向，记作。时，聚类效果较好。假设有一个二维数据集，包含个对象，它们的分布如图所示。算法以区间标度变量为例，对象（，）和对象（，）之间的欧氏距离：（，）%假设数据集有个对象，将其聚为类，密度参数，邻域半径，是半径的调节系数。算法描述如下：（）在数据集中，计算任意两

8、个对象间的相异度（，如果要把它们划分成三类，按照上面的思想寻找初始聚类中心（如图所示）。首先计算数据集中各对象间的相异度，形成相异度矩阵；然后计算各对象的密度，其中对象表示），将它的密度最大，选其作为第一个聚类中心（用“”从数据集中删除。从相异度矩阵中找出其邻域内的所有对象，形成一个簇，并从数据集中删除这些对象。重复上面的步骤，依次找出第二个簇和第三个簇（中心分别用“表”示）。如果规定邻域半径，则包含个对象，包含），形成相异度矩阵；（）；（）根据相异度矩阵确定邻域半径的大小：（）根据定义计算数据集中对象的密度，找到密度最大的对象，作为初始聚类中心，形成簇（），从数据集中删除这个对象；（）在数据

9、集中，根据相异度矩阵找到对象邻域内的对象，将其加入簇，并从数据集中删除；（）重复第（）步直到数据集中再也没有对象邻域内的对象；（），再计算数据集中对象的密度，找到密度最大的对象，作为初始聚类中心，形成簇（）并从数据集中删除这个对象，返回第（）步执行；（）如果数据集中非空，则根据对象的方向定义将中的对象加入合适的簇，反之则视为孤立点。个对象，包含个对象（如图中用实线包围部分）。中还剩余个对象分别为、，其中对象根据对、视为孤立点（与其他对象的最小距离大于半径）。象方向的定义，由于对象与对象的距离最小且小于，而对象属于簇，故对象也属于簇，同理，对象、也属于簇；对象则属于（如图中箭头所示）。这样形最自

10、然”的簇，从而得到成的簇是与实际对象的分布相同，是“了最好的划分效果（如图中虚线所示）。算法性能分析算法的时间复杂度：算法中每次操作都是以矩阵为依据的，即以矩阵中的一行为单位进行，这样可以大大提高算法的速度。该算法的时间主要用于计算相异度矩阵，时间计算机工程与应用中用黑色的“标出），再由邻域半径的公式计算出半径，”最后得到聚类结果如图所示。可以看出，算法可以很好地处理任意形状的数据集，同时也较好地屏蔽了“噪声”和孤立点数据的影响，准确地反映复杂度为（）；由于该算法过程中要用到对象的相异度矩阵，其大小为，数据量大，我们采用了把矩阵存储到硬盘上以节省内存空间。算法中增加的额外开销，是寻找对象方向的

11、计算，只是增加了计算量，并且是基于矩阵的操作，所以其处理不影响算法总的时间复杂度。至于维数的情况，除了计算对象的相异度矩阵的时间会随着维数的增大而增加外，算法中其他部分的计算都不会发生变化，时间复杂度和空间复杂度都不受维数的影响。也就是说，算法中除了相异度计算与维数有关，其余计算是与维数无关，只与对象数目有关。了原有数据的空间几何特征。总结算法是聚类分析中常用的一种方法，但是算法对初始聚类中心的选取依赖性非常强，这样就限制了该算法的性能，本文提出的改进方法，根据数据的自然分布找出聚类中心，找出对象中分布比较密集的区域，这正是聚类的目的，从而摆脱了随机选取聚类中心对聚类结果产生的不稳定性；以及用质心代表一个簇所带来的“噪声”和孤立点数据对聚类结果的影响；同时采用对象的方向方法可以得到任意形状的簇。实验证明改进后的方法是可行而有效的。为了实现真正意义上的无指导聚类，今后我们要进一步研究基于密度的聚类个数的自动确定问题。（收稿日期：年月）实验分析为了验证这种新的改进算法能产生稳定而“自然的”有效聚类结果，我们用实现了算法。实验数据如图所示，共有个点其分布随机产生，其中噪声分布的点占了数据集的。算法执