聚类在数据挖掘中发挥着重要作用，属于非监督学习方法之一。聚类后的数据具有如下特征：类内元素具有最大的相似度，类间元素则拥有最大的区分度^[1]。总体而言，目前的聚类方法可分为划分法^[2-3]、层次法^[4]、模糊理论法^[5-7]、分布法^[8]、密度法^[9-10]、网格法^[11-12]以及一些现代智能方法^[13]。每种聚类方法都有其自身的优势与劣势^[14]。目前应用最为广泛的划分方法如K均值(K-means)法^[2]和K中心点(K-medoids)法^[3]，其缺点是不能处理任意形状数据且需要手动输入类簇个数。层次法往往具有较高的时间复杂度，且需要提前指定类簇个数，如利用层次方法的平衡迭代规约和聚类(balanced iterative reducing and clustering using hierarchies，BIRCH)算法^[4]。模糊c均值(fuzzy c-means，FCM)^[5]是一种典型的模糊聚类方法，其聚类效果敏感于预先设定的类簇个数，其后改进的比较流行的Gustafson-Kessel(GK)模糊聚类^[6]和Gath-Geva(GG)模糊聚类^[7]算法也都未很好解决上述问题。分布法^[8]的前提假设不够充分且时间复杂度较高。含噪声的基于密度聚类方法(density-based spatial clustering of applications with noise，DBSCAN)^[9]及其改进后的点排序识别聚类结构法(ordering point to identify the cluster structure，OPTICS)^[10]是比较流行的密度聚类方法，但当密度分布不均匀时，往往不能得到理想的聚类结果。统计信息网格法(statistical information grid approach，STING)^[11]和小波聚类(WaveCluster，WC)^[12]是网格聚类方法的代表，通过在网格子空间内的计算大大降低了全局运行时间。通过在聚类过程中引入一些智能方法来获取满意的聚类结果是现代智能聚类方法的主要思想^[13]，但这无疑增加了大量的计算成本。基于密度和距离的聚类方法(density and distance based clustering，DDC)^[1]清晰地阐释并应用了聚类基本思想，类簇中心比其邻域元素具有更高的局部密度且与其他具有较高局部密度的元素相距更远。然而，这样的计算耗费了较多时间，且该方法并没有实现真正意义的自动聚类。

综合分析上述各种聚类方法的优缺点，本文提出一种基于邻域关系、局部密度和网格划分的聚类方法，称之为邻域密度网格聚类(neighborhood density grid clustering，NDGC)方法。该方法可实现任意形状数据的自动聚类，自主寻找聚类中心，且具有较低的时间复杂度。本文首先阐述了邻域密度网格聚类算法的基本思想，给出相关定义和理论分析。然后，结合定义和理论给出聚类算法和复杂度分析。在数值实验中，不仅采用人工数据验证NDGC算法的正确性，还利用区域识别数据和其他常用聚类方法验证本文方法的实用性和有效性。最后，对NDGC算法的参数和实验结果进行了讨论分析。

1 邻域密度网格聚类 1.1 基本思想

邻域密度网格聚类方法是一种基于网格划分、局部密度和邻域关系的聚类方法。该方法主要思想是：将原始数据映射到网格子空间并得到每个网格中的数据点分布密度(局部密度)，然后根据邻域关系将网格空间内的网格元素逐步划分到对应的类簇中。在逐层扩展地搜索聚类元素时，利用最大相对距离和最大相对密度原则，寻找潜在的聚类中心，从而实现完全自主的聚类。

该算法的思想源自于三维空间内的等高线山体。每一座独立的山体可视为一个类簇，山峰即为类簇中心，等高线和山峰间相对距离是寻找聚类中心的主要依据。在搜索聚类元素时，从山顶出发，利用邻域关系逐步扩张地添加聚类元素。

对于常见的二维空间正态分布数据(如图 1所示)，利用网格划分可得到其山体式的局部密度分布图(三维空间内等高线山体)，如图 2所示。

图 2中的两座山体可视为对应于图 1中的两个类簇，具有较大局部密度的网格元素即体现为山顶。具有相同局部密度的网格元素可认为在同一等高线范围内(如图 3所示)。

在聚类过程中(如图 3所示)，首先从当前最大局部密度的网格元素(中心1)开始，以某一特定邻域范围为标准，搜索第1批聚类元素(红色圆圈内网格)，然后以搜索后的最大局部密度为标准(等高线标准)，在剩余的网格元素中搜索符合这一标准的候选聚类中心，随后通过最大相对距离原则筛选得到下一个聚类中心(中心2)。在接下来的搜索中，以新增聚类元素(红色圆圈内网格)和新增聚类中心(中心2)为基础，继续逐层扩张地搜索新的元素，直至所有网格元素搜索完毕。

1.2 基本理论

在邻域密度网格聚类算法中，通过引入一种映射关系实现原始数据与网格子空间的关联。

定义1  (映射编码)给定m×n维数据集U及网格个数K。对于U中某一列u_j，其网格区间可表示为$ I = ({\rm{max}}({u_j}) - {\rm{min}}({u_j}))/K$，则任意样本x_ij∈u_j，其对应的映射编码表示为

$ {f_{ij}} = {\rm{floor}}({x_{ij}}/I) + 1. $

(1)

其中：i=1, 2, …, m；floor(·)为向下取整函数，以确保编码f_ij为整数；max(·)和min(·)分别为取最大值和最小值函数。

根据网格个数K映射后的子空间S维度变为K×n维。若K≤m，则子空间S相比原空间U降低了计算复杂度和存储空间。若K>m，则子空间S相对原空间U是扩张的。由于映射后的数据通常呈现稀疏性，因此在一定程度上，映射后的计算复杂度是降低的。

通过定义1的映射，原始数据与子空间网格元素(以下简称元素)具有唯一的对应关系，该对应关系既可以正向(原始空间U对应子空间S)编码，也可以反向(子空间S对应原始空间U)解码。因此，通过定义1的映射，在子空间内的聚类等效于在原始空间内的聚类。

定义2   (局部密度)对于任意子空间网格元素s(s∈S)，其Gauss核函数形式的局部密度表示为

$ {\rho _s} = \sum\limits_{x \in s, {\rm{ }}x \in U} {{\rm{exp}}\left( { - {{\left( {\frac{{{\rm{dist}}(x, {\rm{ }}{s_c})}}{I}} \right)}^2}} \right)} . $

(2)

其中：x为映射到s内的原始样本，s_c为当前网格元素s的中心，dist(·, ·)为某种距离函数，本文选取Euclid距离。

由式(2)可知，当网格区间内较多样本靠近网格中心时，则对应的局部密度较大。

定义3    (邻域)在网格子空间中，对于某一指定网格元素s_i，如果其相邻网格与其距离小于给定阈值d_t，即dist(s_i, s_j) < d_t，则这样的相邻网格元素集合{s_j}称为网格元素s_i的邻域。

根据1.1节中的分析，聚类中心选取原则如下：

1) 初始聚类中心(如图 3中的中心1)为当前网格子空间内具有最大局部密度的网格元素；

2) 非初始聚类中心(如图 3中的中心2)具有最大相对局部密度，该相对局部密度是基于上一轮确定的聚类网格元素中最大的局部密度而言的；

3) 非初始聚类中心具有最大相对距离，该相对距离为当前网格元素与已有聚类中心之间距离之和；

4) 非初始聚类中心至少不应该是下一轮即将被添加的聚类元素；

5) 邻域内聚类中心(用于扩张搜索的网格)是那些上一轮新增的边缘聚类网格元素(如图 3中的红圈内网格元素)；

6) 聚类中心不应为噪声元素。

对于非初始聚类中心选取中的相对局部密度和相对距离，可依据式(3)进行评价,

$ {\gamma _c} = {{\bar \rho }_c} \cdot {{\bar d}_c}. $

(3)

其中：$ {{\bar \rho }_c}$和${{\bar d}_c} $均为规范化后的相对密度和相对距离，$ {{\bar \rho }_c} = {\rho _c}/{\rm{max}}\left( \rho \right), {{\bar d}_c} = \sum\limits_{i = 1}^n {{\rm{dist}}(c, {\rm{ }}{c_i})/(n\cdot{d_{{\rm{max}}}}){\rm{ }}{d_{{\rm{max}}}}} $为当前网格空间内最大相对距离，c_i为已知聚类中心。

对于非初始聚类中心的选取，每次都选取具有最大γ_c的候选聚类中心作为新的聚类中心。当然，若不满足选取原则中的第2条，则在此轮搜索中不新增任何非初始聚类中心。

通常情况下，实际处理的数据中往往会存在噪声，导致聚类效果不理想。在邻域密度网格聚类算法中，局部密度小于某特定值ρ_t且孤立的网格元素s被视为噪声，即ρ_s < ρ_t且{s_j}= $ \phi $，{s_j|dist(s, s_j) < d_t}。根据式(2)可知，若网格元素s中只含有一个样本，max(ρ_s)=1。因此，ρ_t通常取1。

1.3 邻域密度网格聚类算法

基于1.1和1.2节对邻域密度网格聚类算法的定义和讨论，可设计算法如图 4所示。

图 4所示算法的时间复杂度受有效网格数V(非空网格)影响，如果第10步的While循环中每次循环有k个元素被选中，则该算法将运行V/k次。因此，第5—29步的时间复杂度为

$ \begin{array}{l} V + \left( {V - k} \right) + \left( {V - 2k} \right) + \ldots + \\ V - \left( {\frac{V}{k} - 1} \right)k = \frac{{V\left( {V - k} \right)}}{{2k}} + 1. \end{array} $

其他步骤的时间复杂度为O(m)(m为总样本个数)。因此，NDGC算法的时间复杂度可近似为m+V(V－k)/(2k)，远低于多数常见聚类算法^[14]。

2 数值实验 2.1 人工数据实验

本节选取具有任意形状的人工数据集为研究对象，测试NDGC算法的聚类效果。各测试数据具体细节如下：

1) Normal：包含两个正态分布类簇；

2) K4Far2：包含4个类簇，含有噪声；

3) Eyes：包含3个类簇；

4) Clouds：包含4个类簇，含有噪声；

5) Aggregation：包含7个类簇，类簇间有连接且分布均匀；

6) Flame：包含2个类簇，类簇分布均匀且含有噪声。

实验中，网格数K选择在25~70，d_t为0.03~0.06，ρ_t为1。得到的聚类结果如图 5—10所示。

综合图 5—10结果可以看出，NDGC可实现任意形状数据的聚类，且对于Aggregation和Flame这类分布较为均匀、类簇间有连接的情况具有较好的处理能力。图 5、6、10结果表明，NDGC可有效识别噪声数据(红色标记点)。实际上，NDGC的理论和算法分析表明，NDGC可通过多维矩阵处理更高维度的数据，但高维数据不便于图形表示，无法直观展示结果。

2.2 基于区域识别的对比实验

本节通过引入Mopsi定位数据集^[15]来验证NDGC的实际应用效果。Mopsi定位数据集包括某用户截至2012年在芬兰(Finland)活动的定位数据。一个好的聚类算法可有效识别用户位置的类别，根据聚类结果可识别用户的基本信息和生活习性。

为了说明NDGC算法的有效性，本文选取最常用的K-means^[1]、DBSCAN^[9]、FCM^[5]和WC^[12]作为对比算法。根据区域识别的特点，每种方法对应的参数选择如下：K-means中聚类个数为7；DBSCAN中邻域元素个数为5，邻域半径为算法中默认计算方法；FCM中聚类个数为7；在WC中，小波变换方法为bior 2.2，密度阈值为0.1，网格数为120；在NDGC中，网格数K为160，d_t为0.008，ρ_t为1。

用户在Finland地图中的位置数据以红色点标记，如图 11所示。各种方法对应的聚类结果如图 12—16所示。

从图 12—16的聚类结果与图 11的原始数据对比可以看出，K-means、FCM和WC的聚类结果不能得到有用的用户信息。相反，DBSCAN和NDGC完全可以识别出用户常去的地方(黑圈标记)，并且NDGC的聚类效果比DBSCAN更突出。通过对比图 13和16可知，由NDGC得到的聚类结果(黑圈标记)更容易判断出该区域为芬兰的重要城市约恩苏(Joensuu)。因此，可基于上述结果进一步研究该用户信息，即将研究范围缩小至Joensuu。该用户在Joensuu的定位信息(红色点标记)如图 17所示。由于数据源给出的用户实际定位点图和数据信息存在一些差异，使得图 17所示位置信息和后续聚类结果存在偏差，但这不影响聚类实验分析。用户在Joensuu的位置数据聚类结果如图 18—22所示。

从图 18—22的聚类结果与图 17的原始数据对比可以看出，FCM和WC算法没能给出有效的位置识别结果。K-means方法得到的主要聚类区域(如图 18中黑色圆圈标记)较大，通过该聚类结果可以粗略识别出用户的主要活动区域。图 19和22中均有两个主要的聚类区域(黑色圆圈标记)，即通过DBSCAN和NDGC可得到较好的聚类结果。通过与图 18对比可知，图 19和22中黑色圆圈区域为Joensuu的主要商业区，因此可推断该用户主要工作地点在此区域内。图 19和22中另外的黑色椭圆区域包含了较多的居民楼，因此可推断此区域为该用户的生活居住区。值得注意的是，NDGC识别出的椭圆居民区比DBSCAN得到的结果更小一些，更有利于区域识别和用户信息推断。

在区域识别实验中，根据用户的定位信息，利用合适的聚类算法，可以很容易推断出用户信息。如果知道对应的时间戳，还可以进行更多更准确的推断。

3 讨论

NDGC算法中的两个参数，网格数K和邻域阈值d_t, 是影响计算复杂度和聚类结果的主要因素。增大网格数K，计算复杂度将随之增加。由此可知，NDGC在处理特别高维度数据时将出现计算负担。然而，现实中对特别高维度数据的使用频率也很低。参数d_t越小，则类簇划分得越细，2.2节的数值实验证实了这点。

从2.2节中的对比实验结果可以分析出以下结论：对于具有奇异形状和复杂分布的数据(如用户的位置分布数据)，使用单一聚类思想往往得不到理想的聚类结果。这就是K-means、FCM和WC算法不适用于区域识别的原因之一。此外，K-means和FCM对聚类个数的设置也是影响聚类效果的原因之一。但对于本文使用的区域识别数据而言，初始化设置聚类个数为7足以满足对用户一些基本信息的挖掘和推断。此外，除本文提出的邻域密度网格聚类算法外，DBSCAN比其他算法更适合区域识别。DBSCAN聚类效果不如NDGC的主要原因是其聚类思想比较单一，而NDGC融合了网格、密度和邻域搜索思想，使其相比于本文对比的其他方法更适合处理区域识别问题。此外，本文算法比作者之前的成果^[16]增加了对密度的利用，可有效处理重叠性数据，具有更强的鲁棒性和适应性。

4 结论

本文基于网格划分、局部密度和邻域关系提出了一种自动快速聚类方法。该方法根据网格空间中的局部密度和相对距离自动检测聚类中心，利用邻域关系迅速完成聚类。本文首先阐述了邻域密度网格聚类方法的基本思想，随后给出聚类算法及时间复杂度分析。最后，基于人工数据的聚类结果验证了NDGC算法的聚类效果及其可处理任意形状数据的能力，基于区域识别的对比实验进一步验证了NDGC算法的有效性和实用性，验证得出基于多种思想融合的聚类算法更适用于解决区域识别问题。今后的工作将研究进一步减少NDGC算法的时间复杂度并将该方法应用到其他领域中。