论文部分内容阅读
【文章摘要】
文章分析了现有基于网格的聚类算法。使用网格方法的数据分析方法将空间划分为由（超）矩形网格单元组成的网格，然后在网格单元上进行聚类。最后，总结全文并提出基于网格的聚类需要进一步研究的方向。
【关键词】
数据挖掘；网格；聚类
0 引言
聚类分析是数据挖掘中广为研究的课题之一，是从数据中寻找数据间的相似性，并依此对数据进行分类，从而发现数据中隐含的有用信息或知识。
1 网格的定义与划分
网格的基本概念，设A1，A2，…，Ar 是数据集O={O1，O2，…，On }中数据对象的r 个属性的有界定义域，那W=A1 ×A2 ×…×Ar 就是一个r 维空间，将A1，A2，…，Ar 看成是W 的维（属性、字段），则对于一个包含n 个数据点的r 维空间中的数据集O={O1，O2，…，On }，其中Oi ={Oi1，Oi2，…，Oir }（i=1，2，…，n），Oi 的第j 个分量Oij ∈Aj。将W的每一维M等分，即把W分割成个网格单元。
基于网格聚类算法的第一步是划分网格结构，按搜索子空间的策略不同，主要有基于由底向上网格划分方法的算法和基于自顶向下网格划分方法的算法。
1.1 由底向上的划分方法
由底向上的网格划分方法按照用户输入的划分参数（即每维段数ki，1 ≤i ≤d），将数据空间均匀划分为相等大小的网格单元，假设落入同一网格单元内的所有数据点都属于同一个簇，每个网格单元保存落入其内数据的统计信息，比如数据点个数，数据点之和。包含一定数目数据点的网格单元被称为高密度网格单元。
WaveCluster与CLIQUE是采用由底向上网格划分方法的代表性算法。WaveCluster处理低维空间数据，它的性能超越了BIRCH、CLARANS，与DBSCAN等优秀的聚类算法。CLIQUE考虑了高维子空间聚类，但它的时间复杂度较高，需要用户指定全局密度阈值。算法MAFIA对CLIQUE进行了改进，为了减少聚类算法需要处理的网格单元数目，MAFIA将均匀划分网格中每一维上数据分布密度相似的相邻段合并，由此得到一个不均匀划分的网格。这个网格在数据分布较均匀的区域划分粒度大，在数据分布不均匀的区域划分粒度小，这种不均匀划分网格的方法能够提高聚类的质量，被后续的许多算法所采用。
采用由底向上的网格划分方法的优点在于，它能通过对数据的一遍扫描，将数据压缩到一个网格数据结构内，并基于这个网格数据结构，发现任意形状的簇。此外，如果网格单元的粒度较小（即体积较小），那么得到的聚簇的精度较高，但是算法的计算复杂度较大。此外，由底向上的网格方法存在不适合处理高维数据的问题。
1.2 自顶向下的划分方法
自顶向下的网格划分方法采取分治的策略（divide and conquer principle），对数据空间进行递归划分，使问题的规模不断减小。首先将原数据空间划分为几个较大的区域。对于每个得到的区域，划分过程反复执行，直到每个区域包含属于同一个簇的数据点，那么这些区域就是最终的网格单元。基于自顶向下网格方法的聚类算法直接将高密度网格单元识别为一个簇，或是将相连的高密度网格单元识别为簇。
OptiGrid与CLTree是两个典型的基于自顶向下网格划分方法的聚类算法。其中，OptiGrid则是用空间数据分布的密度信息来选择最优划分。通过一个密度函数来决定切割平面，可以将数据空间划分为规则的或不规则单元，与传统的等间距的划分相比，可以用此来解决高维聚类的问题。
自顶向下划分方法的主要优点在于不需要用户指定划分参数，而是根据数据的分布对空间进行划分，因此这种划分更为合理。数据空间维度对自顶向下网格方法的影响较小，可以快速将大型高维数据集中的簇分隔开。这一类方法的计算复杂度与数据集大小和维度都呈线性关系适合于处理高维数据。由于划分是基于数据分布的，而通常认为噪音是在整个空间均匀分布的，所以自顶向下划分方法对噪音不敏感。但是，由于这种方法得到的网格单元的体积远大于由底向上网格方法中的网格单元体积，因此方法产生的簇的描述精度比由底向上的网格方法得到的簇的描述精度要低。而且在自顶向下的划分过程中，同一个簇可能被划分到不同的区域中，最终得到的同一区域也可能包含不同的簇，这样就进一步降低了算法的正确度。这类划分方法的另一个缺点是它在划分过程中，需要对数据集进行多次扫描。
而由底向上划分方法在于只需对数据集进行一次线性扫描以及较高的簇的描述精度。因此，两类方法适用于不同的问题。前者适于处理高维数据集，后者能有效处理存取代价较大的超大型数据集与动态数据。
2 基于网格的聚类过程
基于网格的聚类算法的基本过程是，首先将数据空间W划分为网格单元，将数据对象集O 映射到网格单元中，并计算每个单元的密度。根据用户输入的密度阈值MinPts 判断每个网格单元是否为高密度单元，由邻近的稠密单元组形成簇。
2.1 网格单元的密度
簇就是一个区域，该区域中的点的密度大于与之相邻的区域。在网格数据结构中，由于每个网格单元都有相同的体积，因此网格單元中数据点的密度即是落到单元中的点的个数。据此可以得到稠密网格单元的密度是，设在某一时刻t一个网格单元的密度为density，定义density=单元内的数据点数/数据空间中总的数据点数，设密度阈值为，为用户输入的密度阙值，当density> 时，该网格单元是—个密集网格单元。
相对于稠密网格单元来说，大多数的网格单元包含非常少甚至空的的数据，这一类网格单元被称为稀疏网格单元。大量的稀疏网格单元的存在会极大的降低聚类的速度，需要在聚类之前对稀疏网格单元进行处理，定义稀疏密度阈值为，当density>时，该网格单元是—个稀疏单元。对于稀疏网格单元的处理方法一般采用压缩的方法或者直接删除的方法，如果需要保留稀疏网格单元用于后续处理，可以使用压缩的方法；如果在现有数据的基础之上直接聚类，可以删除稀疏网格单元，理论分析和实验证明删除稀疏网格单元并不影响聚类的质量。
2.2 由稠密网格单元形成簇
在基于网格的聚类算法中，根据以上分析，由邻接的稠密单元形成簇是相对直截了当的，这也是基于网格的方法的优点之一。但是需要首先定义邻接单元的含义。设n维空问中的存在任意两个网格单元U1和U2，当这两个网格单元在—个维上有交集或是具有一个公共面时，称它们为邻接网格单元。
在二维空间中，比较常使用的是4-connection相邻定义和8-connection相邻定义，4-connection更适合在聚类算法中使用。因为当寻找某个网格单元的邻居时，在4-connection定义下，一个网格单元只有2d个邻居，而在8-connection定义下，有3d-1个邻居，当数据维度d较大时，这个数目非常大。使用4-connection不仅参与计算的单元数目大为减少，而且单元增加与维数的关系由指数增长变为线性增长，所以能进一步减少算法运行所需的时间，具有较低的计算复杂度。
3 结论
基于网格的聚类方法目前还存在一些急需解决的问题，主要有以下几点：（1）当簇具有不同的密度时，全局的密度参数不能有效发现这样的簇，需要开发具有可变密度参数的算法。（2）对于不同类型数据的聚类问题。（3）当数据集的规模巨大以及数据具有地理分布特性时，需要开发有效的并行算法来提高处理的速度。（4）对现有网格算法的优化，从不同方面提高网格算法的有效性。
【参考文献】
孙玉芬.基于网格方法的聚类算法研究[J].华中科技大学.2006.
【作者简介】
王运强（1987—），男，辽宁省沈阳人，同济大学软件学院硕士研究生。
文章分析了现有基于网格的聚类算法。使用网格方法的数据分析方法将空间划分为由（超）矩形网格单元组成的网格，然后在网格单元上进行聚类。最后，总结全文并提出基于网格的聚类需要进一步研究的方向。
【关键词】
数据挖掘；网格；聚类
0 引言
聚类分析是数据挖掘中广为研究的课题之一，是从数据中寻找数据间的相似性，并依此对数据进行分类，从而发现数据中隐含的有用信息或知识。
1 网格的定义与划分
网格的基本概念，设A1，A2，…，Ar 是数据集O={O1，O2，…，On }中数据对象的r 个属性的有界定义域，那W=A1 ×A2 ×…×Ar 就是一个r 维空间，将A1，A2，…，Ar 看成是W 的维（属性、字段），则对于一个包含n 个数据点的r 维空间中的数据集O={O1，O2，…，On }，其中Oi ={Oi1，Oi2，…，Oir }（i=1，2，…，n），Oi 的第j 个分量Oij ∈Aj。将W的每一维M等分，即把W分割成个网格单元。
基于网格聚类算法的第一步是划分网格结构，按搜索子空间的策略不同，主要有基于由底向上网格划分方法的算法和基于自顶向下网格划分方法的算法。
1.1 由底向上的划分方法
由底向上的网格划分方法按照用户输入的划分参数（即每维段数ki，1 ≤i ≤d），将数据空间均匀划分为相等大小的网格单元，假设落入同一网格单元内的所有数据点都属于同一个簇，每个网格单元保存落入其内数据的统计信息，比如数据点个数，数据点之和。包含一定数目数据点的网格单元被称为高密度网格单元。
WaveCluster与CLIQUE是采用由底向上网格划分方法的代表性算法。WaveCluster处理低维空间数据，它的性能超越了BIRCH、CLARANS，与DBSCAN等优秀的聚类算法。CLIQUE考虑了高维子空间聚类，但它的时间复杂度较高，需要用户指定全局密度阈值。算法MAFIA对CLIQUE进行了改进，为了减少聚类算法需要处理的网格单元数目，MAFIA将均匀划分网格中每一维上数据分布密度相似的相邻段合并，由此得到一个不均匀划分的网格。这个网格在数据分布较均匀的区域划分粒度大，在数据分布不均匀的区域划分粒度小，这种不均匀划分网格的方法能够提高聚类的质量，被后续的许多算法所采用。
采用由底向上的网格划分方法的优点在于，它能通过对数据的一遍扫描，将数据压缩到一个网格数据结构内，并基于这个网格数据结构，发现任意形状的簇。此外，如果网格单元的粒度较小（即体积较小），那么得到的聚簇的精度较高，但是算法的计算复杂度较大。此外，由底向上的网格方法存在不适合处理高维数据的问题。
1.2 自顶向下的划分方法
自顶向下的网格划分方法采取分治的策略（divide and conquer principle），对数据空间进行递归划分，使问题的规模不断减小。首先将原数据空间划分为几个较大的区域。对于每个得到的区域，划分过程反复执行，直到每个区域包含属于同一个簇的数据点，那么这些区域就是最终的网格单元。基于自顶向下网格方法的聚类算法直接将高密度网格单元识别为一个簇，或是将相连的高密度网格单元识别为簇。
OptiGrid与CLTree是两个典型的基于自顶向下网格划分方法的聚类算法。其中，OptiGrid则是用空间数据分布的密度信息来选择最优划分。通过一个密度函数来决定切割平面，可以将数据空间划分为规则的或不规则单元，与传统的等间距的划分相比，可以用此来解决高维聚类的问题。
自顶向下划分方法的主要优点在于不需要用户指定划分参数，而是根据数据的分布对空间进行划分，因此这种划分更为合理。数据空间维度对自顶向下网格方法的影响较小，可以快速将大型高维数据集中的簇分隔开。这一类方法的计算复杂度与数据集大小和维度都呈线性关系适合于处理高维数据。由于划分是基于数据分布的，而通常认为噪音是在整个空间均匀分布的，所以自顶向下划分方法对噪音不敏感。但是，由于这种方法得到的网格单元的体积远大于由底向上网格方法中的网格单元体积，因此方法产生的簇的描述精度比由底向上的网格方法得到的簇的描述精度要低。而且在自顶向下的划分过程中，同一个簇可能被划分到不同的区域中，最终得到的同一区域也可能包含不同的簇，这样就进一步降低了算法的正确度。这类划分方法的另一个缺点是它在划分过程中，需要对数据集进行多次扫描。
而由底向上划分方法在于只需对数据集进行一次线性扫描以及较高的簇的描述精度。因此，两类方法适用于不同的问题。前者适于处理高维数据集，后者能有效处理存取代价较大的超大型数据集与动态数据。
2 基于网格的聚类过程
基于网格的聚类算法的基本过程是，首先将数据空间W划分为网格单元，将数据对象集O 映射到网格单元中，并计算每个单元的密度。根据用户输入的密度阈值MinPts 判断每个网格单元是否为高密度单元，由邻近的稠密单元组形成簇。
2.1 网格单元的密度
簇就是一个区域，该区域中的点的密度大于与之相邻的区域。在网格数据结构中，由于每个网格单元都有相同的体积，因此网格單元中数据点的密度即是落到单元中的点的个数。据此可以得到稠密网格单元的密度是，设在某一时刻t一个网格单元的密度为density，定义density=单元内的数据点数/数据空间中总的数据点数，设密度阈值为，为用户输入的密度阙值，当density> 时，该网格单元是—个密集网格单元。
相对于稠密网格单元来说，大多数的网格单元包含非常少甚至空的的数据，这一类网格单元被称为稀疏网格单元。大量的稀疏网格单元的存在会极大的降低聚类的速度，需要在聚类之前对稀疏网格单元进行处理，定义稀疏密度阈值为，当density>时，该网格单元是—个稀疏单元。对于稀疏网格单元的处理方法一般采用压缩的方法或者直接删除的方法，如果需要保留稀疏网格单元用于后续处理，可以使用压缩的方法；如果在现有数据的基础之上直接聚类，可以删除稀疏网格单元，理论分析和实验证明删除稀疏网格单元并不影响聚类的质量。
2.2 由稠密网格单元形成簇
在基于网格的聚类算法中，根据以上分析，由邻接的稠密单元形成簇是相对直截了当的，这也是基于网格的方法的优点之一。但是需要首先定义邻接单元的含义。设n维空问中的存在任意两个网格单元U1和U2，当这两个网格单元在—个维上有交集或是具有一个公共面时，称它们为邻接网格单元。
在二维空间中，比较常使用的是4-connection相邻定义和8-connection相邻定义，4-connection更适合在聚类算法中使用。因为当寻找某个网格单元的邻居时，在4-connection定义下，一个网格单元只有2d个邻居，而在8-connection定义下，有3d-1个邻居，当数据维度d较大时，这个数目非常大。使用4-connection不仅参与计算的单元数目大为减少，而且单元增加与维数的关系由指数增长变为线性增长，所以能进一步减少算法运行所需的时间，具有较低的计算复杂度。
3 结论
基于网格的聚类方法目前还存在一些急需解决的问题，主要有以下几点：（1）当簇具有不同的密度时，全局的密度参数不能有效发现这样的簇，需要开发具有可变密度参数的算法。（2）对于不同类型数据的聚类问题。（3）当数据集的规模巨大以及数据具有地理分布特性时，需要开发有效的并行算法来提高处理的速度。（4）对现有网格算法的优化，从不同方面提高网格算法的有效性。
【参考文献】
孙玉芬.基于网格方法的聚类算法研究[J].华中科技大学.2006.
【作者简介】
王运强（1987—），男，辽宁省沈阳人，同济大学软件学院硕士研究生。