基于速度加速度的子空间聚类算法-数学分析论文

聚类分析是数据挖掘中非常活跃的研究领域。聚类是将给定的数据集划分成不同类别（或称为一个聚类），使同一类别中个体的相似度尽可能大，而不同类别中个体的相似度尽可能小。聚类可以发现属性之间所存在的联系，从而找出数据分布的模式，目前它已经广泛应用于模式识别、数据分析、图象处理和市场分析。聚类分析所涉及的领域包括：数据挖掘、统计学、机器学习、空间数据技术、生物学、市场学等。

随着数据量的快速增大，数据往往是具有很多特征，即现实中的数据大多是高维度数据集，而高维度的数据往往是稀疏的（即不存在全部维度上都密集的聚类），又因为聚类算法的时间复杂度往往会随着维度的增加而快速的增大，故而，高维度数据空间中的子空间聚类是很有效的一种获取有用信息的方法。

3 算法实验结果及分析
评估一种边界点检测算法的标准主要有两个方面：算法的有效性（正确性）和执行效率。有效性意味着算法能够准确地检测出聚类的边界点；执行效率高意味着算法不仅可以应用在小型数据集上，而且可以应用到大型数据集上，有很好的扩展性。下面，我们从这两方面对算法做出评估。

3.1有效性分析
我们使用一个数据集的实验结果和一个数据集的理论分析来说明问题。

1、为了直观地说明算法的有效性，本文使用二维数据集进行测试。

原图 CLIQUE          BAS-CLIQUE

图4 两种算法实验结果比较

图4为包含8486个数据对象的数据集，从实验结果可以看出来，CLIQUE把聚类边界的很多数据点归为噪声，造成了精度的下降，这也是很多基于网格的聚类算法都存在的问题即边界的检测问题。而改进后的BAS-CLIQUE算法，在聚类的边界处使用间隔之间数据点个数变化的速度和加速度参数，使聚类边界得到了很好的柔化，能较好地避免边界点的损失，提高聚类精度。

2、数据集理论分析。

我们从理论上的示例数据集来说明算法的效果。

图5在示例数据集上进行理论说明

如图5，使用CLIQUE算法，如果设定的密度阈值过高，则两个菱形中的稀薄区域将不会被包含在聚类中；如果密度阈值过低，则左右两个菱形会被认为是同一个聚类（因为间隔t2的数据点密度比较大，CLIQUE会认为它与t1和t3同属于一个聚类）。

而BAS-CLIQUE加入了速度和加速度参数来增加聚类边界的精确度，由t1、t2到t3，密度变化的趋势为先减后加，加速度会超过给定标准（因为速度的变化比较大），我们会认为t2是聚类的边界；同时在两个菱形的稀薄区域，密度变化的趋势都为逐渐减小，加速度不会超过给定标准，我们会得到较CLIQUE更为精确的聚类形状。

3.2 时间复杂度分析
本算法对CLIQUE算法主要做了两点改进：

1、在每一维查找密集单元时，通过间隔内密度的速度和加速度进行聚类。对每一个满足密度阈值的密集单元进行一次遍历，计算速度和加速度并进行合并，此项操作会增加密集单元的扫描次数，只增加线性的时间复杂度，在总体算法时间复杂度方面没有影响。但此项操作可以有效地减少密集单元的个数(因为生成了自适应间隔，而自适应间隔可能有固定间隔几倍的跨度范围)，进而减少在以后剪枝操作中的遍历次数，在最坏的情况下，即每一个密集间隔与其他密集间隔都不相邻，将会产生与CLIQUE相同的时间复杂度。

2、在剪枝的操作过程中，考虑速度和加速度的因素，会增加线性的时间复杂度，在总体算法时间复杂度方面没有影响。

综上，BAS-CLIQUE相比CLIQUE，时间复杂度相同，通常情况下效率更高一点(最坏情况下与CLIQUE相同O(Cd+md) ，其中m是输入数据点数，C为常数，d是数据空间的维度)。

4结论及进一步工作
本文提出了基于速度加速度的子空间检测算法，该算法基于CLIQUE，在寻找密集单元和剪枝的过程中利用速度和加速度进行了优化，能有效地提高CLIQUE的精确度和计算效率。但本算法增加了一个参数（在本文2.2中表述，加速度参数取速度参数的常数倍数），下一步我们将在更多数据集包括真实数据集上进行实验，以证明算法的有效性，及采取有效措施减小参数对聚类结果的影响。