万方数据２００４年１０月皖西学院学报 Ｏｃｔ． ２００４第２０卷第５期Ｊｏｕｒｎａｌ ｏｆ Ｗｅｓｔ Ａｎｈｕｉ ＵｎｉｖｅｒｓｉｔｙＶｏｌ． ２０ ＮＯ． Ｓ一种基于密度的增量式网格聚类算法苏守宝’，郁书好‘，２（１．皖西学院计算机科学与技术系，安徽六安２３７０１２；２．河海大学计算机信息工程学院，江苏南京２１００９８）摘 要：ｉｔ Ｉ算法的要求是聚类特征一般是可加的、非迭代的。文中提出了一种基于密度的网格聚类算法ＧＤＣＬＵＳ，并在此基础上提出了增圣式算法ＩＧＤＣＬＵＳ，它可发现任意形状的聚类，具有高效、易实现的特点，适用于数据库周期性地增蚤环晚下的数据批量更新。 关键词：聚类；密度；网格；增童算法中图分类号： ＴＰ３１１， ＴＮ９１１． ７２文献标识码：Ａ文章编号：１００９一９７３５（２００４）０５一００９１－０４ 聚类分析是个古老而又年轻的研究领域，聚类技术是数据挖掘研究中的一个非常活跃的研究课题。聚类就是把一个没有类别标记的样本集按某种准则划分成若干类，使类内样本的相似性尽可能大，而类间样本相似性尽量小，是一种无监督的分类方法。聚类技术已被广泛地应用于计算机视觉、模糊控制、模式识别、数据挖掘、决策分析和预测等许多领域。在越来越多的应用中，需要对大规模、高维数据进行聚类，有的应用中由于数据规模太大，不能一次性处理；有的应用中数据库在不断更新。聚类能发现大型数据库中潜在的有用模式，但是经过一系列数据库后更新这些模式可能会过时、有可能导致错误的决策支持，所以保持模式更新是很重要的。由于大规模数据库及聚类算法的高时间复杂性，非常期望进行增量更新，而且增量更新时无需每次（聚类时）均对整个数据库进行处理而只对数据库中的增量部分数据进行处理即可完成聚类，并对已有的聚类结果进行增量式修改与完善。传统的统计聚类分析方法包括层次聚类法、分裂法、聚合法、动态聚类法、有序样品聚类、有重叠聚类和模 糊聚类等川，这些聚类方法是一种基于全局比较的聚类，它需要考察所有的个体才能决定类的划分，因此它要求所有的数据必须预先给定，而不能动态增加新的数据对象。一个有效的算法应该能对现有的聚类进行增量地插人和删除，它要求聚类特征必须是可加的，如ＢＩＲＣＨ和改进的ｋ一ｍｅａｎｓ聚类特征三元组ＣＦ（样本数量Ｎ，线性和，平方和ＳＳ）［２１、 ＣＯＢＷＥＢ中的概念的属性值等都具有单调可加性，ＣＬＡＳＳＩＴ是对ＣＯＢＷＥＢ的扩展，用来处理连续性数据的增量聚类算法［［３］。增量聚类有适应大规模、动态数据、降低内存需求、可实现并行处理等诸多好处，且增量算法需要的空间小，仅对类的重心是必需的叫。这些算法的代表性特征是非迭代的，因此它们所需要的时间也很少，但是即使把迭代引人增量聚类算法中，其计算复杂度和所需的相应时间也不会显著增加〔“，“〕。但是增量算法对数据库的更新非常敏感，甚至一个数据点的增加或删除都可能会引起类的合并或分裂。增量算法是把存储在辅助存储器里的数据，一次一个数据项集转到内存里进行聚类，为了缓解空间的限制，也可把类的表述固定不变地保留在内存中。由于增量聚类是在不同数据子集上进行的，需要解决的是在每一次或一个子集中聚类时要保存多少信息、子聚类中如何组织信息及维护信息的效率如何等问题。１相关研究基于网格划分的聚类算法由于其易于增量实现而被广泛地应用于数据挖掘之中。迄今为止， 人们已经提来收稿日期：２００４一０８一１８ 作者简介：苏守宝（１９６５一），男，安徽六安人，硕士，副教授，主要研究方向：计算智能与数据挖掘；郁书好（１９７６一），男，硕士，讲师，主要研究方向：语义Ｗｅｂ与数据挖掘。出了一些基于密度和网格的聚类算法如ＤＢＳＣＡＮ，ＣＵＲＥ，ＣＰ，ＣＬＩＱＵＥ，ＤＢＣＡ等，这些算法都试图通过不同的途径实现对大规模数据库的有效聚类，尽管人们不断地构建各种聚类算法，但总的来说，面对急剧增长的大规模数据库能显示特别效率的聚类算法并不多。ＣＬＩ ＱＵＥ是一种基于网格和密度的聚类算法［２７，它是一种更广泛的子空间聚类方法，可以通过维度的任意组合来产生子空间，再将数据投影到子空间中进行聚类，具有网格类算法效率高的优点，并且可以处理高维的数据。但是不可避免地具有网格聚类算法的缺点，即在划分网格时没有或者很少考虑数据的分布，而且用一个网格内的统计信息来代替该网格内的所有点，从而导致了聚类质量的降低。文献川提出了采用数据空间网格划分的基于密度的聚类算法的均值近似方法。该方法过滤并释放位于稠密超方格中的数据项，并利用其重心点近似计算其对周围数据元素的影响因子，给出均值近似在聚类算法中的实现策略及其误差估计。均值近似方法在减少内存需求、降低计算复杂度方面取得了一定的效果。ＩＧＤＣＡ［ｓ］是一种基于密度的增量式网格聚万方数据类算法，该算法通过将数据空间划分成体积相等的若干单元，然后对单元而不是对数据点进行聚类，只有密度不小于给定的闹值１的单元之间距离不大于给定阑值２的单元格才被聚为一类。本文受ＣＬＩ ＱＵＥ， ＩＧＤＣＡ等的启发，提出了一种基于密度的网格聚类算法ＧＤＣＬＵＳ，并在ＧＤＣＬＵＳ的基础上进一步提出了基于密度的增量式网格聚类算法，具有较高的聚类效率而且容易实现，可以发现任意形状的聚类并适用于数据的批量更新。２一种基于密度和网格的聚类算法—ＧＤＣＬＵＳ 在基于密度的算法中，所谓一个聚类就是一个比周围区域（Ｒｅｇｉｏｎ）有更高的数据点密度的区域。为了识别数据点的密度，我们将数据空间进行划分（ｐａｒｔｉｏｎ）并找出数据点划分的每个单元（ｕｎｉｔ）中的数据点的数目。为了使得计算点的密度的方法简单一些，我们将数据空间分割成网格（ｇｒｉｄ）状（这是通过将数据空间中的每一维划分成相同的区间数来做到的，这就意味着每一个单元具有相同的“体积”，这样单元中点的密度的计算可以转换成简单的点计数），然后把落到某个单元中的点的个数作为该单元的密度（ｄｅｎｓｉｔｙ）。这时可以指定一个阂值：，当某单元格中得点的个数大于该阑值时，就说这个单元格（ｕｎｉｔ）是密集的，然后，聚类也就是所有紧相邻近的密集单元格的集合。紧相连接的单元格是指彼此有公共面的那些单元格，而不考虑单元格的质心或重心间的距离达到另一个距离阑值。２．１相关概念 设Ａ＝ ｛Ｄ１，Ｄ２，．－，Ｄ．｝是ｎ个有界定义域，那么Ｓ＝Ｄ，ＸＤ２ｘ．．． ｘＤ。就是一个ｎ维空间，我们将ＤＩ， Ｄ２，．．．，Ｄ。看成是Ｓ的维（属性、字段）；算法的输人是一个ｎ维空间中的点集，设为Ｖ＝ ｛ｖ１，ｖ２，－，ＶＪ，其中ｖｉ一｛Ｖｉ ｌｉ ， ｖ；ｚ，一ｖｉｎ ｆ ｏ ｖｉ的第Ｊ个分量ｖｉ． ＥＤ；；通过一个输人参数资，黝可以将空间Ｓ的每一维分成相同的之个区间，从而将整个空间分成了有限个不相交的超矩形单元（ｃｅｌｌｓ），假设维是有序的，维的划分间隔确图１二维空间中单元格及定后，可以用：ｕ（１１．１１２ｎ．）来描述网格单元的位置，其中１１．，１２．，一Ｉｎ其４个最近邻示意图 是维的属性值序列。定义１（ 密度）：若１维上用间隔ｍｉ分成等长的母段，一个点ｖ二卜１．， Ｖ２，一、｝落人一个区间”一｛ｕ１， Ｕ＞，．．． ， Ｕｎ ｌ，当且仅当对于每一个ｕ；都有ｌ；＜ ＝ｖ；＜ｈ；成立。假定每个单位体积看成是１，定义一个单元格ｕ的密度ｄｅｎｓｉｔｙ（ｕ）＝落人单元格中的数据点数。当ｄｅｎｓｉｔｙ（ ｕ） ＝ ０时，ｕ称为空单元；当ｄｅｎｓｉｔｙ（ｕ） ＞０时，ｕ称为非空单元。 定义２（密集的）：对于用户的输入参数：，称数据单元格ｕ是密集的（ｄｅｎｓｅ），当且仅当，ｄｅｎｓｉｔｙ（ ｕ） ＞ ｒ；否则ｕ是非密集的（ｎｏｎ一ｄｅｎｓｅ）．定义３（邻接单元与聚类）： 一个聚类（ｃｌｕｓｔｅｒ）是在ｋ维空间中由一个或多个密集的的邻近单元格的最大并集；两个ｋ维中的单元格ｕｔ，ｕ：称为邻接的（ｎｅｉｇｈｂｏｒｉｎｇ）当且仅当这两个单元格有一个公共的面。两个单元格ｕ１一｛Ｒ，，，Ｒ，，，．．．，Ｒ，，ｌ，ｕ２＝ｌＲｔ，，Ｒｔ２，．．．，Ｒｔｋ｝有一个公共的面是指，存在ｋ一１个维度（不妨设这ｋ－１维就是万方数据ｔＩＩｔｚ，．．．，ｔｋ－１），有ＲｔＪ．＝ Ｒ＇ ，』成立（ｉ＝１，２，．．．，ｋ），并且对于第ｔｋ维有ｈ，、一ｌ＇ ｔｋ，或者ｈ＂ｔ、一ｌ＂成立。ｎ维空间中的每个单元格有＜２ｎ个邻近单元格，如图３一１所示，二维空间中的单元格可以有４个近邻单元格。定义４（最大区域）： 称区域Ｒ包含于一个聚类Ｃ，当且仅当ＲｎＣ＝Ｒ；Ｒ是最大的（ｍａｘｉｍａｌ）当且仅当没有一个Ｒ的超集Ｒ也包含于Ｃ；一个聚类Ｃ的最小描述是上述“最大区域（ｍａｘｉｍａｌ ｒｅｇｉｏｎ）”的一个集合ｒ， ｒ中的最大区域刚好覆盖Ｃ，并且为了满足覆盖的条件，集合ｒ中的最大区域的个数不能再减少了。定义５（噪声） 令｛Ｃｌ，ｑ，＂，Ｃｋ｝是数据空间Ｄ的一组聚类的集合，Ｃｎｏｉｓｅ为噪声单元集，它不属于任何类，有所Ｃｎｏｉｓｅ中各个单元上的点是噪声。２．２ ＧＤＣＬＵＳ算法描述ＧＤＣＬＵＳ算法一般分三个步骤如图３一２所示： 数据聚类结果图２ ＧＤＣＬＵＳ算法的一般步骤其算法描述如下：Ｓｔ ｅｐｌ：设置阑值Ｔ及预处理，对输入的数据空间Ｄ及给定的每维上的间隔数任，划分单元格，并统计每个单元格内的点数，即单元格的密度；得到所有非空单元格信息，并按维的次序作为关键字排序，存储单元格位置一、密度、非空单元数及ｋ一ｄ树指针。Ｓｔ ｅｐ２：对输人的密度阑值Ｔ，把０＜ ｄｅｎｓｉｔｙ＜ ｒ的单元格作为Ｃｎｏｉｓｅ，而对所有ｄｅｎｓｉｔｙ ＞ ｒ的单元格进行聚类，处理办法是从第一个未聚类的单元ｕ开始使用ＢＦＳ，搜索单元ｕ的所有（＜２ｎ个）邻接单元ｎｅｉｇｈｂｏｒｈｏｏｄ（ｕ），如果其中有１个已被聚类，则ｕ及其所有邻接单元均记为同一聚类ＩＤ；如果其密度单元均未被聚类，则标识为新类ＩＤ。读取下一个未聚类的单元直到所有密集单元均已聚类。Ｓｔ ｅｐ３：将所有数据点映射为其相应单元的聚类ＩＤｏ２．３ ＧＤＣＬＵＳ的时间复杂性ＧＤＣＬＵＳ不象ＤＢＳＣＡＮ那样搜索。 ｏｒｅ或边界点的每个邻近点，也不象ＧＤＣＡ那样去计算密度可达的单元间的距离，对于每一个访问的密集单元，算法仅搜索它的＜２ｋ个的相邻单元。若密集单元总数为ｎ，则数据结构访问总数为２ｋｎ。而且ＣＤＣＬＵＳ只考虑ｄｅｎｓｉｔｙ（ｕ）：的单元，考虑高维空间数据稀疏的特点，密集单元数Ｃｄ与数据空间中数据点数Ｎ成线性关系且Ｃｄ ＜ Ｎ，所以ＧＤＣＬＵＳ的时间复杂性是Ｏ（Ｎ＋ ＩＣｄ Ｉ ｌｏｇＣｎｏｎｅｍｐｔｙ Ｉ）所以ＧＤＣＬＵＳ可适用于高维数据空间，而且有较好的效率。一般地，对于一个给定的密度阑值，密集单元数不可能非常大，因此假设算法中的密集单元都存储在内存中，则对数据结构的访问效率很高的。３ ＩＧＤＣＬＵＳ一基于ＧＤＣＬＵＳ的增ｆ算法 如果已经得到了使用ＧＤＣＬＵＳ的聚类集，当新增加或删除数据时，原有的聚类必须修改以反映相应的变化。由于单元更新可以看作是一系列的插人与删除，一个单元的更新则至少有一个点增加或删除，由于插人或删除的点仅影响对应单元的密度，可以用单元来替代点进行成批地插人或删除。经过插人后， 有的非密集单元可能成为密集的；而删除后，有的密集单元可能成为非密集的，这种单元密度特性的改变将导致聚类情形的改变，引起聚类的分裂、合并甚至产生新的类。即使更新过的单元仍保持其密度特性，但它原来的聚类状况仍有可能由于邻接单元的密度特性的变化而改变。在ＧＤＣＬＵＳ的基础上，增量算法ＩＧＤＣＬＵＳ的算法思想描述如下：Ｓｔ ｅｐｌ：发现更新单元。在数据库的增量部分，用ＧＤＣＬＵＳ的预处．理办法能发现密度特性已经发生改变的那些单元。Ｓｔ ｅｐ２：修改受影响的聚类。９３ （Ｉ）如果新的非空单元ｃ是密集的，并人和它的任何邻近单元同类，否则创建一个新类；（ ２）吸收一些原是噪声或非空单元的而成为密度单元的；（３）两个聚类与新增加的密集单元邻近， 将它们合并。（４）一些有损失密度的单元会导致聚类的分裂，改变邻近单元的聚类标哀Ｉ Ｄ． 增量数据越大、分布越广，受影响的单元越多即需要更新的聚类ＩＤ的单元越多，尤其Ｓｔｅｐ２的第（４）种情况，聚类的分裂将是一个耗时的过程，不过幸运的是，增加和插入数据总比删除要频繁得多，而且通过ＩＧＤ－万方数据ＣＬＵＳ对已有聚类进行更新，比ＧＤＣＬＵＳ在整个数据库上的聚类更有效率。ＩＧＤＣＬＵＳ适用于数据库周期性地增量的环境下的数据的批量更新。４结语 随着聚类分析对象数据集规模的急剧增大，改进现有算法以获得满意的效率受到越来越多的重视，对大规模、高维数据库的高效聚类分析依然是个有待研究的开放问题。在实际应用中，特别是面对现实的数据集中含有高维的对象，几乎所有的聚类算法中要求输人的参数值都难以确定，而且算法对这些参数值非常敏感，参数的稍微改动会引起数据集的划分变动特别大；高维数据的实际分布经常是不对称的，聚类算法只使用一个全局参数无法很好地刻画真实的聚类结构；数据库内容的不断更新使得某些已完成的聚类结果变得过时等等这些问题都影响了聚类算法的有效性，高效、自适应性和交互性地、动态地增量式的聚类算法有待进一步研究。参考文献：［１］ Ｖｉｊａｙａ， Ｐ． Ａ． Ｎａｒａｓｉｍｈａ Ｍｕｒｔｙ， Ｍ． Ｓｕｂｒａｍａｎｉａｎ， Ｄ． Ｋ． Ｌｅａｄｅｒｓ－Ｓｕｂｌｅａｄｅｒｓ：Ａｎ ｅｆｆｉｃｉｅｎｔ ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｌａｒｇｅ ｄａ－ ｔａ ｓｅｔｓ． Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｌｅｔｔｅｒｓ． Ｍａｒ２００４， Ｖｏｌ． ２５ Ｉｓｓｕｅ ４， ｐ５０５， ９ｐ．［ ２ ］ Ｈａｎ Ｊ， Ｋａｍｂｅｒ Ｍ． Ｄａｔａ Ｍｉｎｉｎｇ Ｃｏｎｃｅｐｔｓ ａｎｄ Ｔｅｃｈｎｉｑｕｅｓ， Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ， Ｓａｎ Ｆｒａｎｃｉｓｃｏ， ２０００．［ ３ ］ Ｈａｎｄ Ｄ， Ｍａｎｎｉｌａ Ｈ， Ｓｍｉｔｈ Ｐ． Ｐｒｉｎｃｉｐｌｅ ｏｆ Ｄａｔａ Ｍｉｎｉｎｇ， ＭＩＴ Ｐｒｅｓｓ， Ｃａｍｂｒｉｄｇｅ： ＭＡ， ２００１［ ４１Ｍｅｈｅｄ Ｋａｎｔａｒｄｚｉｃ． Ｄａｔａ Ｍｉｎｉｎｇ Ｃｏｎｃｅｐｔｓ， Ｍｏｄｅｌｓ， Ｍｅｔｈｏｄｓ ａｎｄ Ａｌｇｏｒｉｔｈｍｓ， ｂｙ Ｌｏｕｉｓｖｉｌｌｅ： ＩＥＥＥ Ｐｒｅｓｓ， ２００２［ ５ ］ Ｂｏｒｕｔ， Ｋｏｌｉｎｇｅｒｏｖｎ， Ｉｖａｎａ． Ａｎ ｉｎｃｒｅｍｅｎｔａｌ ｃｏｎｓｔｒｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｄｅｌａｎｅｙ ｔｒｉａｎｇｕｌａｔｉｏｎ ｕｓｉｎｇ ｔｈｅ ｎｅａｒｅｓｔ一ｐｏｉｎｔ ｐａｒａｄｉｇｍ， Ｉｎｔｅｒ－ｎａｔ ｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｇｅｏｇｒａｐｈｉｃａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ； Ｍａｒ２００３， Ｖｏ１１７， Ｉｓｓｕｅ ２， ｐ１１９，２０ｐ．［６） Ｃｈａｒｉｋａｒ， Ｍｏｓｅｓ Ｐａｎｉｇｒａｈｙ， Ｒｉｎａ， Ｃｌｕｓｔｅｒｉｎｇ ｔｏ ｍｉｎｉｍｉｚｅ ｔｈｅ ｓｕｍ ｏｆ ｃｌｕｓｔｅｒ ｄｉａｍｅｔｅｒｓ． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ＆Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ；Ｍａｒ ２００４， Ｖｏｌ． ６８， Ｉｓｓｕｅ ２， ｐ４１７ ， ２５ｐ ．［７］ＬＩ Ｃｕｎ一Ｈｕａ，ＳＵＮ Ｚｈｉ一Ｈｕｉ，Ａ Ｍｅａｎ Ａｐｐｒｏｘｉｍａｔｉｏｎ Ａｐｐｒｏａｃｈ ｔｏ ａ Ｃｌａｓｓ ｏｆ Ｇｒｉｄ一Ｂａｓｅｄ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍｓ， Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔ－ｗａｒ ｅ， Ｃｈｉｎａ ， Ｊ ｕ１２００３ ， Ｖｏ１１４， Ｉｓｓｕｅ７， ｐ１２６７，１５ｐ． （Ａｂｓｔｒａｃｔ ｉｎ Ｃｈｉｎｅｓｅ）．［８１ＣＨＥＮ Ｎｉｎｇ，ＣＨＥＮ Ａｎ， ＺＨＯＵ Ｌｏｎｇ一ｘｉａｎｇ． Ａｎ Ｉｎｃｒｅｍｅｎｔａｌ Ｇｒｉｄ Ｄｅｎｓｉｔｙ一Ｂａｓｅｄ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ． Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ， Ｃｈｉ－ｎａ； Ｊａｎ２００２，Ｖｏｌ１３，Ｉｓｓｕｅ１，ｐ１，７ｐ． （Ａｂｓｔｒａｃｔ ｉｎ Ｃｈｉｎｅｓｅ）． Ａｎ Ｉｎｃｒｅｍｅｎｔａｌ Ｇｒｉｄ Ｄｅｎｓｉｔｙ一Ｂａｓｅｄ Ｃｌｕｓｔｅｒｉｎｇ ＡｌｇｏｒｉｔｈｍＳｕ Ｓｈｏｕｂａｏｌ，Ｙｕ Ｓｈｕｈａｏ１，２ （１．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｗｅｓｔ Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｌｕ’ａｎ ２３７０１２，Ｃｈｉｎａ；２．Ｓｃ ｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ Ｉｎｆｏｒｍａｔｉｏｎ＆Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｅｈａｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａ可ｉｎ ２１００９８，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ： Ｉｎｃｒｅｍｅｎｔａｌ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｅａｔｕｒｅｄ ｎｏｒｍａｌｌｙ ｉｎ ａｄｄａｂｌｅ ａｎｄ ｎｏｎ－ｉｔｅｒａｔｉｖｅ． Ｔｈｉｓ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｓ ａ ｇｒｉｄ ｄｅｎｓｉｔｙ－ｂａｓｅｄ ｃｌｕｓ－ｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ－ ＧＤＣＬＵＳ，ａｎｄ ａｎ ｉｎｃｒｅｍｅｎｔａｌ ａｌｇｏｒｉｔｈｍ－ＩＧＤＣＬＵＳ，ｗｈｉｃｈ ｃａｎ ｆｉｎｄ ｈｉｇｈ ｅｆｆｅｃｔｉｖｅｌｙ ａｒｂｉｔｒａｒｙ ｓｈａｐｅ ｃｌｕｓｔｅｒｓ，ａｎｄ ｉｓ ａｐｐｌｉ－ｃａｂｌｅ ｉｎ ｐｅｒｉｏｄｉｃａｌｌｙ ｉｎｃｒｅｍｅｎｔａｌ ｅｎｖｉｒｏｎｍｅｎｔ．Ｋｅｙ ｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ；ｄｅｎｓｉｔｙ；ｇｒｉｄ；ｉｎｃｒｅｍｅｎｔａｌ ａｌｇｏｒｉｔｈｍ