基于凝聚层次聚类的co—location模式挖掘

第２９卷第２期　广西师范大学学报：自然科学版　Ｖｏ１．２９　Ｎｏ．２　２０１１年６月　Ｊｏｕｒｎａｌ　ｏｆ　Ｇｕａｎｇｘｉ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ：Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ　Ｊｕｎ．２０１１　基于凝聚层次聚类的　ＣＯ—ｌｏｃａｔｉｏｎ模式挖掘　高世健，王丽珍，冯岭，陈红梅　（云南大学信息学院，云南昆明６５００９１）　摘要：空间的ＣＯ—ｌｏｃａｔｉｏｎ模式代表一组空间对象的子集，它们的实例在空间中频繁地关联，它是空间数据　挖掘的重要研究方向。本文首先介绍ＣＯ—ｌｏｃａｔｉｏｎ模式挖掘的基本算法，然后提出一种新的挖掘算法，算法先　对空间数据进行凝聚层次聚类，在聚类结果上挖掘ＣＯ—ｌｏｃａｔｉｏｎ模式，最后对这种新的算法作实验评估。　关键词：空间数据挖掘；ｃ０一ｌｏｃａｔｉｏｎ模式；凝聚层次聚类；参与度　中图分类号：ＴＰ３９２　文献标识码：Ａ　文章编号：１００１　６６００（２０１１）０２—０１６７—０７　０　引言　随着空间数据应用越来越广泛，空间数据挖掘也引起了很多学者的关注。空间数据挖掘是从空间数据　库中发现潜在的、有用的知识过程。空间ＣＯ—ｌｏｃａｔｉｏｎ模式是代表着一组空间对象的子集，它们的实例在空　间中频繁地关联。挖掘ＣＯ—ｌｏｃａｔｉｏｎ模式就是在空间数据库中挖掘空间对象之间的空间关联关系［１］。在现　实世界中，也存在着很多空间ＣＯ—ｌｏｃａｔｉｏｎ模式，例如，生态学家发现尼罗河鳄鱼和埃及珩鸟的生活空间相　互重叠；植物学家根据共生植被的分布，发现“半湿润常绿阔叶林”生长的地方８Ｏ　有“兰类”植物生长。移　动运营商可以根据不同客户需求的分布，把相关的套餐搭配在一起以达到增加收入的目的。其他方面还包　括地球科学、公共卫生、公共交通等［２引。　在挖掘空间ＣＯ—ｌｏｃａｔｉｏｎ模式方面，Ｓ．Ｓｈｅｋｈａｒ和Ｙ．Ｈｕａｎｇ在文献［６］中提出最小参与率概念的ｊｏｉｎ—　ｂａｓｅｄ算法，该算法具有类Ａｐｒｉｏｒｉ性质。文献［７］则提出了基于部分连接的算法。可是当数据量较大时，连　接运算的时间开销非常大，于是文献［８］进一步提出基于无连接的算法。Ｍ．Ｃｅｌｉｋ等人提出了研究区域ＣＯ—　ｌｏｃａｔｉｏｎ模式挖掘的思路［９］。而Ｙ．Ｈｕａｎｇ等人在文献［－１０］中首次提及了聚类与空间ＣＯ—ｌｏｃａｔｉｏｎ模式之间　的内在联系，阐述基于聚类技术挖掘空间ＣＯ—ｌｏｃａｔｉｏｎ模式的思想。文献［－１１］讨论一种类似于多分辨剪枝　思想的基于密度的挖掘方法。文献［１２］提出了一种基于ｏｒｄｅｒ—ｃｌｉｑｕｅ的挖掘思想，而后在总结和分析一些　典型挖掘算法的基础上提出了基于前缀树结构的挖掘算法［１引。　本文受文献［１０］的启发，把凝聚层次聚类算法引入到空间ＣＯ—ｌｏｃａｔｉｏｎ模式挖掘中来。与文献［６］中的　方法不同，在空间数据集中，先用凝聚层次聚类算法对所有属性分别进行聚类，然后计算各属性所有簇之　间的粗邻近关系，在具有粗邻近关系的簇中求出其二阶频繁模式，在此基础上再计算更高阶的ＣＯ—ｌｏｃａｔｉｏｎ　模式。　１　相关定义　定义一组空间属性的集合Ｆ，这些属性的实例集合　，定义在Ｓ之上的空间关系Ｒ。其中Ｒ可以是空　间拓扑关系、距离关系或混合关系等。如果一对空间实例满足空间关系尺，那么用实线把这一对空间实例　连接起来，如图１所示。图１包含３个空间对象Ａ、Ｂ、Ｃ，每一个点代表了一个空间对象的唯一的实　收稿日期：２０１１—０５—０７　基金项目：国家自然科学基金资助项目（６１０６３００８）；云南省教育厅研究基金资助项目（０９Ｙ００４８）；云南大学科学研究基　金资助项目（２００９Ｆ２９Ｑ）　通讯联系人：王丽珍（１９６２一），女，云南丽江人，云南大学教授，博士。Ｅ—ｍａｉｌ：ｌｚｈｗａｎｇ２００５＠１２６．ｃｏｒｎ　１６８　广西师范大学学报：自然科学版　第２９卷　例。如Ａ．１代表空间对象　的第１个实例。两个实例满足Ｒ当且仅当它们的欧几里德距离小于等于ｄ，　即可以表示为：　Ｒ（Ａ．１，Ｂ．１）㈢（ｄｉｓｔａｎｃｅ（　．１，Ｂ．１）≤　）。　设有空间集Ｊ＝｛ｉ　，ｉ　，…，　），如果有｛Ｒ（ｉ　，ｉｋ）Ｉ　１≤　≤ｚ，１≤忌≤ｚ｝，则称ｊ是一个团。…一个空间ＣＯ—ｌｏ—　ｃａｔｉｏｎ模式是一组空间对象的集合Ｃ，其中ｃ　Ｆ。　如图１中｛Ａ，Ｂ，ｃ）就是一个ＣＯ—ｌｏｃａｔｉｏｎ模式。一个ＣＯ—ｌｏｃａｔｉｏｎ模式Ｃ的长度称为ＣＯ—ｌｏｃａｔｉｏｎ模式的　阶，即ＣＯ—ｌｏｃａｔｉｏｎ模式里空间对象的个数，记作ｓｉｚｅ（ｃ）＝＝＝ｌｆｌ。如果团　包含了ＣＯ—ｌｏｃａｔｉｏｎ模式ｃ中的所有　属性，并且　没有任何一个子集可以包含ｃ中的所有属性，那么　是ＣＯ—ｌｏｃａｔｉｏｎ模式ｃ的一个行实例（称　为ＣＯ—ｌｏｃａｔｉｏｎ实例）。Ｃｏ—ｌｏｃａｔｉｏｎ模式ｆ的所有行实例的集合称为表实例。　在空间数据中衡量ＣＯ—ｌｏｃａｔｉｏｎ模式的有趣程度所使用的支持度标准称为参与度ＰＩ（ｐａｒｔｉｃｉｐａｔｉｏｎ　ｉｎ—　ｄｅｘ），它是所有空间属性参与率ＰＲ（ｐａｒｔｉｃｉｐａｔｉｏｎ　ｒａｔｉｏｎ）值中的最小值。设　是某个空间属性，　在ｋ阶　ＣＯ—ｌｏｃａｔｉｏｎ模式（＇一｛ｆ　．．，＾）中的参与率表示为ＰＲ（ｆ，ｆｉ），它是　的实例在空间ＣＯ—ｌｏｃａｔｉｏｎ模式Ｃ的　所有实例中不重复出现的个数与　中总实例个数的比率，公式如下：　ＰＲ（ｆ，／　）＝＝＝　其中７ｒ是投影操作。那么，参与度ＰＩ（ｃ）就可以用ＰＩ（ｃ）一ｍｉｎ　｛ＰＲ（ｃ，ｆｉ））计算了。　例ｌ在图１中，对象Ａ有４个实例，对象Ｂ有５个实例，对象ｃ有３个实例，对象Ｄ有２个实例。ＣＯ—　ｌｏｃａｔｉｏｎ模式ｆ＝｛Ａ，Ｂ，Ｃ｝的表实例有｛｛Ａ．２，Ｂ．４，ｃ．２｝，｛Ａ．３，Ｂ．３，Ｃ．１｝｝。因为在Ａ的４个实例中只有　Ａ．２和Ａ．３出现在表实例中，所以ＰＲ（ｃ，Ａ）一２／４。类似地，ＰＲ（ｃ，Ｂ）一２／５，ＰＲ（ｃ，ｃ）：２／３。最终ＰＩ（ｃ）一　ｍｉｎ（ＰＲ（ｃ，　），ＰＲ（ｆ，Ｂ），ＰＲ（ｃ，ｃ））一２／５＝＝＝０．４。若设ｒａｉｎ—ｐｒｅｙ是用户给定的最小参与度阈值，那么当　ＰＩ（ｆ）≥ｒａｉｎ—ｐｒｅｖ时，称ＣＯ—ｌｏｃａｔｉｏｎ模式ｆ是频繁的。参与率和参与度随着ＣＯ—ｌｏｃａｔｉｏｎ模式阶的增大而　单调递减＿６ｊ。　图１　空间属性及空间实例示例　Ｆｉｇ．１　Ｓｐａｔｉａｌ　ａｔｔｒｉｂｕｔｅ　ａｎｄ　ｓｐａｔｉａｌ　ｉｎｓｔａｎｃｅｓ　图２空间数据分布示例图　Ｆｉｇ．２　Ｅｘａｍｐｌｅ　ｃｈａｒｔ　ｏｆ　ｓｐａｔｉａｌ　ｄａｔａ　ｄｉｓｔｒｉｂｕｔｉｏｎ　２基于凝聚层次聚类的挖掘算法　本节先阐述一下凝聚层次聚类算法，然后提出基于该聚类的ＣＯ—ｌｏｃａｔｉｏｎ模式挖掘算法，最后给出这　个算法的时间复杂度分析。　２．１凝聚层次聚类算法　常见的聚类方法有ｋ均值算法、凝聚层次聚类算法、ＤＢＳＣＡＮ算法等。本文采用凝聚层次聚类算法作　为挖掘空间ＣＯ—ｌｏｃａｔｉｏｎ模式的一个数据预处理手段。因为ｋ均值算法需要用户指定聚类生成ｋ个簇，针对　不同的数据分布，ｋ值大小的选取很难。而ＤＢＳＣＡＮ算法对于高维数据，它的密度定义很困难。凝聚层次　聚类算法只需要用户指定一个距离阈值，算法就可以根据不同的数据分布自动生成聚类。尽管它的时间复　第２期　高世健等：基于凝聚层次聚类的ｃｏ—ｌｏｃａｔｉｏｎ模式挖掘　１６９　杂度比ｋ均值要高，但是相对ｋ均值算法来说，噪声和离群数据对凝聚层次聚类算法的影响比较小。　凝聚层次聚类算法的核心思想是：从个体点作为簇开始，相继合并两个最接近的簇，直至只剩下一个　簇。算法的关键操作是计算两个簇之间的邻近度。常见的簇的邻近度的定义有单链、全链、组平均、Ｗａｒｄ　方法和质心方法。我们采用质心方法来衡量两个簇的邻近度。即如果两个簇的质心的距离小于用户指定　的距离阈值，并且这个距离又是所有簇对之间的最小值，那么这两个簇就合并成一个簇。相对于其他方法，　质心方法时间耗费相对较少。比如，有两个簇的成员个数分别是　和ｎ，求两个质心的距离的时间复杂度　为ｏ（　＋　），而单链、全链和组平均等方法都需要计算两个簇所有成员两两之间距离才能确定下来，它们　的时间复杂度都是Ｏ（ｎｍ），而且在本文中聚类只是一个数据预处理的手段，并不需要太精确的聚类结果，　所以采用质心方法相对合理。　２．２基于凝聚层次聚类的挖掘算法　如图２所示，空间属性　有５个实例，属性Ｂ有７个实例，属性Ｃ有５个实例。分别对这３个空间属　性进行聚类，然后把聚类结果按各个簇的成员个数降序排列。结果如图３箭头１所示。在各个簇中求出簇　内所有成员离质心距离最远的点，把这个距离称为簇的半径ｒ。再以簇的质心为圆心，以ｒ为半径画圆，如　果两圆圆心距离减去两圆半径之和小于等于用户指定的距离阈值ｄ，称这两个簇满足粗邻近关系。即　Ｒ（ｃｉ，　）∞（ｄｉｓｔａｎｃｅ（ｃｉ，ｃｉ）一ｒ　一　）≤　。　（１）　式（１）中距离邻近关系采用欧几里德距离来衡量。从几何上看，Ｉｄｉｓｔａｎｃｅ（　ｃｐ—　—ｒ　ｌ就是两个圆的最　小距离，如果连最小距离都大于阈值ｄ，两个圆内的任意两个实例的距离肯定也大于ｄ。换言之，当式（１）　成立时，两个簇内有可能存在着距离小于ｄ的两个实例，但式（１）不成立时，两个簇不可能存在距离小于ｄ　的实例。另外，Ｉｄｉｓｔａｎｃｅ（　Ｃｊ）一　一　Ｉ的值有以下几种情况：①大于０，说明两个圆不相交；②等于０，说明　两个圆相切，那么式（１）一定成立；③小于０，说明两个圆有重叠部分，式（１）也一定成立。我们把满足粗邻　近关系的簇称为粗实例。在连接满足粗邻近关系的簇之后，计算每个属性的参与率上界。对于每一个空间　属性，如果它在某个模式中的参与率上界小于最小参与度阈值，就可以把这个候选模式剪枝，理由如引理　１和引理２所示。　引理１粗实例的参与度大于等于实际参与度。　证明　假设有两个属性厂１和厂２，它们有若干个簇对的距离小于等于距离阈值ｄ，那么它们的参与率　上界是所有簇成员总数与实例总数的比率，参与度是两个参与率上界的较小值。又假设对于任意的两个实　例厂　和厂２ｆ，如果Ｒ（ｆ　ｆ２　）≤　，那么这两个实例必定属于若干个簇对中的其中一个。而厂１粗实例的参与　度是考虑了所有簇的成员都有厂２的实例到它的距离小于等于ｄ，这些簇的成员必定包含了　；同理，厂２　空间属性及其实例　聚类及按簇成员个数降序排列结果　口　Ｃ　Ｃ　墓鐾薹　空　间　属　性　之　『ＨＪ　的　实　例　ｌ　１　连　属性之间满足粗邻近关系　接　４／７　ｌ　图３基于聚类结果的ＣＯ—ｌｏｃａｔｉｏｎ模式挖掘过程　Ｆｉｇ．３　Ｐｒｏｃｅｓｓ　ｏｆ　ｍｉｎｉｎｇ　ＣＯ—ｌｏｃａｔｉｏｎ　ｐａｔｔｅｒｎｓ　ｂａｓｅｄ　ｏｎ　ｃｌｕｓｔｅｒｉｎｇ　ｒｅｓｕｌｔ　１７０　广西师范大学学报：自然科学版　第２９卷　亦然。所以粗实例的参与度一定大于等于实际参与度。证毕。　引理２候选模式中只要有一个属性的参与率上界小于最小参与度阈值，整个模式都被剪枝。　证明　假设有某候选模式｛　，厂　），　的参与率上界小于最小参与度阈值，又有　的参与率上界小于　厂ｆ的参与率上界，由参与度的定义可知，模式｛　，厂　的参与度等于　的参与率上界，所以模式｛　，，，）被　剪枝；又假设　的参与率上界大于　的参与率上界，模式｛　，　｝的参与度就等于厂，的参与率上界，根据　不等式传递律，厂　的参与率上界必定小于最小参与度阚值，模式被剪枝，引理得证。　如图３所示，对于｛　，Ｂ），满足粗邻近关系的属性Ａ的簇有簇ｌ和簇３，这两个簇的成员总和为３，Ａ　的实例总数有５个，假设这两个簇所有成员与属性Ｂ都满足空间邻近关系Ｒ，那么属性Ａ的参与率上界　为３／５。类似地，属性Ｂ的参与率上界为５／７。假设用户指定的最小参与度阈值为５Ｏ　９／５，两个属性的参与率　上界皆大于阈值，下一步将进行实例连接。通过连接属性Ａ的一号簇与属性Ｂ的一号簇，求出二阶ＣＯ一１ｏ—　ｃａｔｉｏｎ候选模式｛Ａ，Ｂ）有实例｛Ａ．１，Ｂ．１）和｛Ａ．１，Ｂ．２｝。这时属性　和属性Ｂ的参与率上界分别为２／５　和３／７，这两个值都小于阈值５Ｏ％，这时就可以对候选实例｛　，引　进行剪枝，没有必要再继续做下面的连　接计算。这也反映了在聚类完成后按簇的成员个数降序排列的作用，把成员多的簇较早进行连接计算，就　可以使得它的参与率上界下降得比较快，如果降到最小参与度阈值以下，就有可能在实例连接的早期把整　个候选模式剪枝。至此，候选模式｛Ａ，引－计算完毕，继续计算模式｛Ａ，Ｃ），只有属性Ａ的三号簇与属性ｃ　的三号簇满足粗邻近关系，它们的参与率上界分别是１／５和１／５，二者皆小于５Ｏ　，候选模式｛　，Ｃ｝就被　剪枝。最后计算候选模式｛Ｂ，Ｃ｝，它们的参与率上界都是１，进行实例连接，如上面所述，每连接完一个簇　对，都要分别计算两个属性的参与率上界，只有二者皆大于参与度阈值才能继续往下计算，否则模式被剪　枝。连接过程不再赘述，候选模式｛Ｂ，Ｃ｝在完成所有的簇对连接后它们的参与率上界分别为４／７和１，取其　中较小值４／７，它大于阈值５Ｏ　，所以候选模式｛Ｂ，Ｃ）是频繁ＣＯ—ｌｏｃａｔｉｏｎ模式。因为模式｛　，引　和｛Ａ，Ｃ｝　都被剪枝了，所以模式｛Ａ，Ｂ，Ｃ｝肯定不是频繁ＣＯ—ｌｏｃａｔｉｏｎ模式。　．　假设最小参与度阈值很低，只有１０　９／５，那么在此例子中，｛Ａ，Ｂ）、｛Ａ，Ｃ）和｛Ｂ，Ｃ｝都是频繁的ＣＯ—ｌｏｃａ—　ｔｉｏｎ模式。紧接着计算三阶候选实例。类似地，首先找出三个属性之间两两满足粗邻近关系的簇，通过查找　得到属性Ａ的三号簇、属性Ｂ的三号簇和属性Ｃ的三号簇两两满足粗邻近关系。它们的参与率上界分别　为１／５、１／７和１／５，均大于阈值。再通过连接得到实例｛Ａ．３，Ｂ．７，Ｃ．５｝，它由模式｛Ａ．３，Ｂ．７｝、｛Ａ．３，Ｃ．５）　和｛Ｂ．７，Ｃ．５）通过两个前１阶的相同的２阶模式连接生成。它的参与度为１／７，所以候选模式｛Ａ．３，Ｂ．７，　Ｃ．５）是一个频繁的ＣＯ—ｌｏｃａｔｉｏｎ模式。　２．３算法的完整描述　ｐｒｅｖ：最小参与度阈值。　输出：频繁ＣＯ—ｌｏｃａｔｉｏｎ模式。　变量：Ｃ＾：ｋ阶ＣＯ—ｌｏｃａｔｉｏｎ候选集；Ｐ＾：ｋ阶ＣＯ—ｌｏｃａｔｉｏｎ频繁集。ｐｒｅｖ：参与率上界。　步骤：　输入：ｄ　：簇合并距离阈值；Ｆ：空间属性的集合；Ｓ：空间实例的集合；ｄ。：邻近关系距离阈值；ｍｉｎ～　①指定ｄ　；　②ｒｅｐｅａｔ　（ｉ）合并最近的两个簇；　（ｉｉ）更新邻近性矩阵，以反映新的簇与原来的簇之间的邻近关系；　ｕｎｔｉｌ最近的两个簇的距离大于ｄ　；　③求各属性之间满足粗邻近关系的簇；　④计算各属性的参与率上界ｐｒｅｙ，对于任意一个属性，如果有ｐｒｅｖ￣ｍｉｎ—ｐｒｅｖ的候选模式剪枝；　⑤对满足实例间的距离≤　的实例存入二阶ＣＯ—ｌｏｃａｔｉｏｎ模式的候选集Ｃ。，每连接完一个簇对就计算　两个属性的参与率上界，并计算候选模式参与度，对参与度＜ｍ　—ｐｒｅｙ的候选模式剪枝；　⑥对于每个ｃ∈Ｃ２，计算Ｐ２（ｆ），如果Ｐ２（ｃ）≥ｍｉｎ—ｐｒｅｖ，把ｆ放入Ｐ２中；　⑦利用两两邻近的簇组重复步骤⑥和步骤⑦，求出Ｐ。；　第２期　高世健等：基于凝聚层次聚类的ＣＯ—ｌｏｃａｔｉｏｎ模式挖掘　⑧反复迭代直至最高阶或某一阶的频繁集为空；　⑨ｒｅｔｕｒｎ　ＵＰ』。　２．４算法的复杂度分析　聚类前要建立一个反映各实例邻近度的矩阵，假设空间属性的数目为　，其中ｍ为　个空间属性的最　大实例数，那它建立邻近度矩阵需要Ｏ（ｍ。）时间。如果邻近度矩阵采用线性搜索，则对于第ｉ次迭代，上述　算法中的步骤②（ｉ）需要０（（　—　＋１）。）时间，步骤②（ｉｉ）仅仅需要０（　一　＋１）的时间，所以聚类的时间　复杂度就是Ｏ（ｍ。）。那么所有的空间属性聚类所耗费的总时间不超过Ｏ（ｎｍ。）。　在聚类完成后，生成是阶ＣＯ—ｌｏｃａｔｉｏｎ频繁候选模式的时间主要花费在模式剪枝和实例生成上。假设，　Ⅳ是志一１阶频繁模式的总数目。候选模式生成之后需要计算各模式的参与度上界ｐｒｅｖ，并把小于最小参　与度阈值的模式剪枝，假设愚阶候选的数目为　，Ｇ是第ｉ个候选模式簇组的数目。　是第ｉ个候选模式　Ｍ　ｑ　．　第　个簇的成员个数，那么它所需要的时间是Ｏ（ｋ×∑∑ｃ　）。接下来生成ｋ阶实例，需要时间Ｏ（ｋ×　ｌ一１　Ｊ一１　Ｍ　∑Ⅱ　）。　算法总时间可以分为聚类时间和生成ＣＯ—ｌｏｃａｔｉｏｎ的时间，表示如下：　Ｍ　ｑ　Ｍ　Ｏ（ｎｍ。）＋（）（足×∑∑　，』・一　＿一　　）＋０（　×∑Ⅱ　。－一儿　。　　３实验分析　实验在模拟数据上进行，算法用ｃ＋＋实现，程序在Ｗｉｎｄｏｗｓ　ＸＰ　ＳＰ３系统，Ｖｉｓｕａｌ　Ｃ＋＋６．０环境　下编译。计算机配置如下，ＣＰＵ：Ｉｎｔｅｌ　Ｃｏｒｅ２　Ｄｕｏ　Ｅ７４００＠２．８０　ＧＨｚ，内存２　ＧＢ。　数据在二维空间Ｅ０，ｌＯ０－］×Ｅｏ，ｌＯＯ－］中随机产生。实验参数如下：空间属性数１０，空间实例数８　０００，簇　合并距离阈值２０，最小参与度阈值ｍｉｎ—ｐｒｅｖ一３ｏ　，实例连接距离阈值５（不指明被改变时）。　图４显示的是空间实例数对算法执行时间的影响。在其他参数不变的情况下，空间实例数变大，时间　也将随着逐渐增大，假如我们用ｊｏｉｎ—ｂａｓｅｄ来代表执行ｊｏｉｎ—ｂａｓｅｄ算法所需要时间，用ＡＨＣ—ｂａｓｅｄ来代表　执行基于凝聚层次聚类挖掘空间ＣＯ—ｌｏｃａｔｉｏｎ模式算法所需要的时间，那么从图中可以看出ＡＨＣ—ｂａｓｅｄ算　法表现出更好的性能。　空间实例数　实例连接距离阈值　图４空间实例数对算法的影响　Ｆｉｇ．４　Ｓｃａｌａｂｉｌｉｔｙ　ｗｉｔｈ　ｉｎｓｔａｎｃｅｓ　ｏｖｅｒ　ｔｗｏ　ａｌｇｏｒｉｔｈｍｓ　图５实例连接距离阈值对算法的影响　Ｆｉｇ．５　Ｓｃａｌａｂｉｌｉｔｙ　ｗｉｔｈ　ｄｉｓｔａｎｃｅ　ｔｈｒｅｓｈｏｌｄ　ｏｖｅｒ　ｔｗｏ　ａｌｇｏｒｉｔｈｍｓ　图５考察的是实例连接的距离阈值ｄ。对算法的影响，在其他参数不变时，ｄ。值越大，ＣＯ—ｌｏｃａｔｉｏｎ实例　数越来越多，算法复杂性也越高。但是从图５中可以看出，ＡＨＣ—ｂａｓｅｄ算法所耗费的时间明显低于ｊｏｉｎ—　ｂａｓｅｄ算法。　图６考察的是最小参与度阈值ｒａｉｎ—ｐｒｅｖ对算法的影响，在其他参数不变的情况下，ｒａｉｎ—ｐｒｅｙ值越　１７２　广西师范大学学报：自然科学版　第２９卷　大，则频繁ＣＯ—ｌｏｃａｔｉｏｎ模式数越少，算法所耗费的时间也就越少。从图６中可以知道，ｍｉｎ—ｐｒｅｙ值越小的　时候，ＡＨＣ—ｂａｓｅｄ算法的优势越明显。　８００　１６０　６００　１２０　４００　８０　２００　４０　０　０．１　Ｏ．２　０．３　０．４　０　ｌＯ　２Ｏ　３Ｏ　４０　最小参与度闽值ｍｉｎｐｒｅｖ　＿簇合并阈值ｄ　图６最小参与度阈值ｍｉｎ—ｐｒｅｖ对算法的影响　Ｆｉｇ．６　Ｓｃａｌａｂｉｌｉｔｙ　ｗｉｔｈ　ｐｒｅｖａｌｅｎｃｅ　ｔｈｒｅｓｈｏｌｄ　ｍｉｎｏｖｅｒ　ｔｗｏ　ａｌｇｏｒｉｔｈｍｓ　—图７簇合并阈值ｄ　对算法的影响　Ｆｉｇ．７　Ｓｃａｌａｂｉｌｉｔｙ　ｗｉｔｈ　ｄｉｓｔａｎｃｅ　ｔｈｒｅｓｈｏｌｄ　ｏｆ　ｍｅｒｇｅｒ　ｃｌｕｓｔｅｒｓ　ｏｖｅｒ　ｔｗｏ　ａｌｇｏｒｉｔｈｍｓ　ｐｒｅｖ　还有一个参数聚类距离阈值ｄ　需要注意。从理论上分析，如果ｄ　值越小，则聚类算法终止越快，但是　生成的簇就越多，后面的连接计算则要耗费多点时间。反过来，ｄ　值越大，则聚类算法耗费时间比较多，连　接计算所需的时间则有可能少一点。图７所示的是当空间实例数为８　０００，最小参与度阈值ｍｉｎ—ｐｒｅｙ为　３０　时，实例连接距离阈值设为５时，簇合并距离阈值ｄ　对算法执行时间的影响。从图中可以看出随着ｄ　的增大，聚类时间略微增长，但是并不明显，而ＡＨＣ—ｂａｓｅｄ算法耗费总时间总体趋于稳定。　４结语　本文在介绍挖掘ｃｏ—ｌｏｃａｔｉｏｎ模式基本算法的基础上，提出一种新的基于凝聚层次聚类的ｃｏ—ｌｏｃａｔｉｏｎ　模式挖掘算法。新算法在生成的结果簇中搜索生成ｃｏ—ｌｏｃａｔｉｏｎ模式。未来将把此思想用于挖掘不确定数　据集中的ｃｏ—ｌｏｃａｔｉｏｎ模式。　参考文献：　Ｅｌｉ　包玉珍，王丽珍，周丽华．空间ＣＯ—ｌｏｃａｔｉｏｎ模式挖掘算法介绍及应用ＥＪ３．郑州大学学报：理学版，２００７，３９（３）：８４—８８．　Ａ—ｚｈｅｎ，ＢＡ０　Ｙｕ—ｚｈｅｎ，ＬＵ　Ｊｏａｎ，ｅｔ　ａ１．Ａ　ｗｅｂ—ｂａｓｅｄ　ｖｉｓｕａｌ　ｓｐａｔｉａｌ　ＣＯ—ｌｏｃａｔｉｏｎ　ｐａｔｔｅｒｎｓ’ｍｉｎｉｎｇ　ｐｒｏｔｏｔｙｐｅ　ｓｙｓ—　Ｅ２］　ＷＡＮＧ　Ｉｔｅｍ（ＳＣＰＭｉｎｅｒ）［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　２００８　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ＣｙｂｅｒＷｏｒｌｄｓ．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ　Ｐｒｅｓｓ，２００８：６７５—６８１．　ＭＯＴＯ　Ｙ．Ｍｉｎｉｎｇ　ｆｒｅｑｕｅｎｔ　ｎｅｉｇｈｂｏｒｉｎｇ　ｃｌａｓｓ　ｓｅｔｓ　ｉｎ　ｓｐａｔｉａｌ　ｄａｔａｂａｓｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　Ｓｅｖｅｎｔｈ　ＡＣＭ　［３］　ＭＯＲＩＳＩＧＫＤＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００１：３５３—３５８．　［４］　ＨＡＮ　Ｊｉａ—ｗｅｉ，ＫＡＭＢＥＲ　Ｍ．Ｄａｔａ　ｍｉｎｉｎｇ：ｃｏｎｃｅｐｔｓ　ａｎｄ　ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．２ｎｄ　ｅｄ．Ｂｅｉｊｉｎｇ：Ｃｈｉｎａ　Ｍａｃｈｉｎｅ　Ｐｒｅｓｓ，２００６．　等．数据仓库与数据挖掘原理及应用ＥＭ］．北京：科学出版社，２００９：２１８—２２６．　Ｅ５］　王丽珍，周丽华，陈红梅，ｓｃｏｖｅｒｉｎｇ　ｃｏ－ｌｏｃａｔｉｏｎ　ｐａｔｔｅｒｎｓ　ｆｒｏｍ　ｓｐａｔｉａｌ　ｄａｔａ　ｓｅｔｓ．ａ　ｇｅｎｅｒａｌ　ａｐｐｒｏａｃｈ　［６］　ＨＵＡＮＧ　Ｙａｎ，ＳＨＥＫＨＡＲ　Ｓ，ＸＩＯＮＧ　Ｈｕｉ．Ｄｉ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００４，１６（１２）：１４７２—１４８５．　　Ｓ，ＳＨＥＫＨＡＲ　Ｓ，ＳＭＩＴＨ　Ｊ，ｅｔ　ａ１．Ａ　ｐａｒｔｉａｌ　ｊｏｉｎ　ａｐｐｒｏａｃｈ　ｆｏｒ　ｍｉｎｉｎｇ　ｃｏ－ｌｏｃａｔｉｏｎ　ｐａｔｔｅｒｎｓＥｃ］／／Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　［７］　ＹＯ０　Ｊｔｈｅ　１２ｔｈ　Ａｎｎｕａｌ　ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ａｎｄ　Ｇｅｏｇｒａｐｈｉｃ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００４：　２４１－２４９．　Ｊ　Ｓ，ＳＨＥＫＨＡＲ　Ｓ，ＣＥＬＩＫ　Ｍ．Ａ　ｊｏｉｎ—ｌｅｓｓ　ａｐｐｒｏａｃｈ　ｆｏｒ　ＣＯ—ｌｏｃａｔｉｏｎ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ：ａ　ｓｕｍｍａｒｙ　ｏｆ　ｒｅｓｕｌｔｓＥｃ］／／　Ｅ８３　ＹＯ０　Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　５ｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ（ＩＣＤＭ　２００５）．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ　Ｐｒｅｓｓ，２００５：８１３—８１６．　　ＩＫ　Ｍ，ＫＡＮＧ　Ｊ　Ｍ，ＳＨＥＫＨＡＲ　Ｓ．Ｚｏｎａｌ　ＣＯ—ｌｏｃａｔｉｏｎ　ｐａｔｔｅｒｎ　ｄｉｓｃｏｖｅｒｙ　ｗｉｔｈ　ｄｙｎａｍｉｃ　ｐａｒａｍｅｔｅｒｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇ　［９］　ＣＥＩ第２期　高世健等：基于凝聚层次聚类的ＣＯ—ｌｏｃａｔｉｏｎ模式挖掘　１７３　ｏｆ　ｔｈｅ　７ｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ（ＩＣＤＭ　２００７）．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ　Ｐｒｅｓｓ，２００７：４３３－４３８．　［１Ｏ３　ＨＵＡＮＧ　Ｙａｎ，ＺＨＡＮＧ　Ｐｕ—ｓｈｅｎｇ．Ｏｎ　ｔｈｅ　ｒｅｌａｔｉｏｎｓｈｉｐｓ　ｂｅｔｗｅｅｎ　ｃｌｕｓｔｅｒｉｎｇ　ａｎｄ　ｓｐａｔｉａｌ　ＣＯ—ｌｏｃａｔｉｏｎ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　１　８ｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｔｏｏｌｓ　ｗｉｔｈ　Ａｒｔｉｆｉｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ（ＩＣＴＡ１　０６）．Ｐｉｓ—　ｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ　Ｐｒｅｓｓ，２００６：５１３—５２２．　［１１］ＸＩＡＯ　Ｘｉａｎｇ—ｙｅ，ＸＩＥ　Ｘｉｎｇ，ＬＵＯ　Ｑｉｏｎｇ，ｅｔ　ａ１．Ｄｅｎｓｉｔｙ　ｂａｓｅｄ　ＣＯ—ｌｏｃａｔｉｏｎ　ｐａｔｔｅｒｎ　ｄｉｓｃｏｖｅｒｙ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　１６ｔｈ　ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ａｄｖａｎｃｅｓ　ｉｎ　Ｇｅｏｇｒａｐｈｉｃ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ（ＧＩＳ’０８）．Ｉｒｖｉｎｅ，ＣＡ：ＡＣＭ　Ｐｒｅｓｓ，２００８：１ｌ一２Ｏ．　［１２３　ＷＡＮＧ　Ｌｉ—ｚｈｅｎ，ＺＨＯＵ　Ｌｉ—ｈｕａ，ＬＵ　Ｊｏａｎ．Ａｎ　ｏｒｄｅｒ—ｃｌｉｑｕｅ—ｂａｓｅｄ　ａｐｐｒｏａｃｈ　ｆｏｒ　ｍｉｎｉｎｇ　ｍａｘｉｍａｌ　ＣＯ—ｌｏｃａｔｉｏｎ［Ｊ］．Ｉｎｆｏｒ—　ｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ，２００９，１７９（１９）：３３７０—３３８２．　［１３］王丽珍，陆叶，陈红梅，等．基于前缀树结构的空间ＣＯ—ｌｏｃａｔｉｏｎ模式挖掘算法研究［Ｊ］．计算机研究与发展，２０１０，４７　（Ｓ１）：３７０—３７７．　Ｃｏ—ｌｏｃａｔｉｏｎ　Ｐａｔｔｅｒｎｓ　Ｍｉｎｉｎｇ　Ｂａｓｅｄ　ｏｎ　Ａｇｇｌｏｍｅｒａｔｉｖｅ　Ｈｉｅｒａｒｃｈｉｃａｌ　Ｃｌｕｓｔｅｒｉｎｇ　ＧＡＯ　Ｓｈｉ—ｊｉａｎ，ＷＡＮＧ　Ｌｉ—ｚｈｅｎ，ＦＥＮＧ　Ｌｉｎｇ，ＣＨＥＮ　Ｈｏｎｇ－ｍｅｉ　（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｙｕｎｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｋｕｎｍｉｎｇ　Ｙｕｎｎａｎ　６５００９１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｓｐａｔｉａｌ　ＣＯ—ｌｏｃａｔｉｏｎ　ｐａｔｔｅｒｎｓ　ｒｅｐｒｅｓｅｎｔ　ｔｈｅ　ｓｕｂｓｅｔｓ　ｏｆ　ｆｅａｔｕｒｅｓ　ｗｈｏｓｅ　ｉｎｓｔａｎｃｅｓ　ａｒｅ　ｆｒｅｑｕｅｎｔｌｙ　ｌｏ—　ｃａｔｅｄ　ｔｏｇｅｔｈｅｒ　ｉｎ　ｇｅｏｇｒａｐｈｉｃ　ｓｐａｃｅ．Ｉｔ　ｉｓ　ａｎ　ｉｍｐｏｒｔａｎｔ　ｒｅｓｅａｒｃｈ　ｉｎ　ｔｈｅ　ｓｐａｔｉａｌ　ｄａｔａ　ｍｉｎｉｎｇ．Ｆｉｒｓｔｌｙ，ｔｈｉｓ　ｐａ—　ｐｅｒ　ｉｎｔｒｏｄｕｃｅｓ　ｔｈｅ　ｂａｓｉｃ　ａｌｇｏｒｉｔｈｍｓ　ｏｆ　ＣＯ—ｌｏｃａｔｉｏｎ　ｍｉｎｉｎｇ．Ｓｅｃｏｎｄｌｙ，ａ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ　ｃｌｕｓｔｅｒｓ　ｔｈｅ　ｓｐａｔｉａｌ　ｄａｔａ　ｂｙ　ｔｈｅ　ａｇｇｌｏｍｅｒａｔｉｖｅ　ｈｉｅｒａｒｃｈｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ｍｉｎｅｓ　ＣＯ—ｌｏｃａｔｉｏｎ　ｐａｔｔｅｒｎｓ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　ｒｅｓｕｌｔ．Ｆｉｎａｌｌｙ，ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｅｖａｌｕａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ａｒｅ　ｐｒｅｓｅｎｔｅｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｓｐａｔｉａｌ　ｄａｔａ　ｍｉｎｉｎｇ；ＣＯ—ｌｏｃａｔｉｏｎ　ｐａｔｔｅｒｎｓ；ａｇｇｌｏｍｅｒａｔｉｖｅ　ｈｉｅｒａｒｃｈｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ；ｐａｒｔｉｃｉｐａｔｉｏｎ　ｉｎｄｅｘ　（责任编辑黄勇）