第３７卷 第１８期 、，０ｌ３７ ・计算机工程 ２０１１年９月 Ｓｅｐｔｅｍｂｅｒ ２０１ １ ＮＯ．１８ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ 软件技术与数据库・ 文章编号：１ｏ００＿＿＿３４２８（２ｏ１１）１８—０ｏ３８—＿０３ 文献标识码：Ａ 中圈分类号：Ｎ９４５ 基于空间布局约束的拓扑关联规则挖掘 方刚 （重庆三峡学院数学与计算机科学学院，重庆４０４０００） 摘要：在空间拓扑关联挖掘中，为提取包含指定空间布局关系的拓扑关联规则，提出一种基于空间布局约束的拓扑关联规则挖掘算法， 该算法能够在多空间关系模式下，挖掘包含空间布局约束的拓扑关联规则，将空间关系事务转换成整数，通过空间布局约束重构非目标空 间对象类的权值向量，用重构权位值递减构建候选频繁项，并用布尔运算计算其支持数。实验结果表明，与传统挖掘算法相比，该算法的 挖掘速度更快、更有效。 关健词：拓扑关联；空间布局约束；向量重构；重构权位值；空间数据挖掘 Ｔｏｐｏｌｏｇｙ Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅ Ｍｉｎｉｎｇ Ｂａｓｅｄ ０ｎ Ｓｐａｔｉａｌ Ｌａｙｏｕｔ Ｃｏｎｓｔｒａｉｎｔ ＦＡＮＧＧａｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｃｈｏｎｇｑｉｎｇ Ｔｈｒｅｅ Ｇｏｒｇｅｓ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ ４０４０００，Ｃｈｉｎａ） ］Ａｂｓｔｒａｃｔ］Ｉｎ ｓｐａｔｉａｌ ｔｏｐｏｌｏｇｙ ａｓｓｏｃｉａｔｉｏｎ ｍｉｎｉｎｇ，ｉｎ ｏｒｄｅｒ ｔｏ ｅｘｔｒａｃｔ ｔｏｐｏｌｏｇｙ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅ ｗｉｔｈ ｇｉｖｅｎ ｓｐａｔｉａｌ ｌａｙｏｕｔ ｒｅｌａｔｉｏｎ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｔｏｐｏｌｏｇｙ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅ ｍｉｎｉｎｇ ｂａｓｅｄ ｏｎ ｓｐａｔｉａｌ ｌａｙｏｕｔ ｃｏｎｓｔｒａｉｎｔ，ｗｈｉｃｈ ｉｓ ａｂｌｅ ｔｏ ｅｘｔｒａｃｔ ｔｏｐｏｌｏｇｙ ａｓｓｏｃｉａｔｉｏｎ ｕｌｒｅ ｗｉｔｈ ｓｐａｔｉａｌ ｌａｙｏｕｔ ｃｏｎｓｔｒａｉｎｔ ｉｎ ｍｕｌｔｉ—ｓｐａｔｉａｌ ｒｅｌａｔｉｏｎ ｐａｔｔｅｒｎｓ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｔｕｒｎｓ ｓｐａｔｉａｌ ｒｅｌａｔｉｏｎ ｔｒａｎｓａｃｔｉｏｎ ｉｎｔｏ ｉｎｔｅｇｅｒ，ａｎｄ ｒｅｆａｃｔｏｒｓ ｗｅｉｇｈｔ ｖｅｃｔｏｒ ｏｆ ｎｏｎ—ｔａｒｇｅｔ ｓｐａｔｉａｌ ｏｂｊｅｃｔ ｃｌａｓｓ ｖｉａ ｓｐａｔｉａｌ ｌａｙｏｕｔ ｃｏｎｓｔｒａｉｎｔ，ａｎｄ ｄｅｃｒｅａｓｅｓ ｒｅｆａｃｔｏｒｉｎｇ ｗｅｉｇｈｔ ｖａｌｕｅ ｔｏ ｇｅｎｅｒａｔｅ ｃａｎｄｉｄａｔｅ ｆｒｅｑｕｅｎｔ ｉｔｅｍ ｓｅｔ，ａｎｄ ｃｏｍｐｕｔｅｓ ｉｔｓ ｓｕｐｐｏｒｔ ｖｉａ Ｂｏｏｌｅａｎ ｏｐｅｒａｔｉｏｎ．Ｗｈｅｎ ｍｉｎｉｎｇ ｔｏｐｏｌｏｇｙ ａｓｓｏｃｉａｔｉｏｎ ｕｌｒｅ ｗｉｔｈ ｇｉｖｅｎ ｓｐａｔｉａｌ ｌａｙｏｕｔ ｒｅｌａｔｉｏｎ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｆａｓｔｅｒ ａｎｄ ｍｏｒｅ ｅｆｉｃｉｆｅｎｔ ｔｈａｎ ｔｒａｄｉｔｉｏｎａｌ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｂｙ ｔｈｅｓｅ ｗａｙｓ． ］Ｋｅｙ ｗｏｒｄｓ］ｔｏｐｏｌｏｇｙ ａｓｓｏｃｉａｔｉｏｎ；ｓｐａｔｉａｌ ｌａｙｏｕｔ ｃｏｎｓｔｒａｉｎｔ；ｖｅｃｔｏｒ ｒｅｆａｃｔｏｒｉｎｇ；ｒｅｆａｃｔｏｒｉｎｇ ｗｅｉｇｈｔ；ｓｐａｔｉａｌ ｄａｔａ ｍｉｎｉｎｇ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００—３４２８．２０１１．１８．０１３ １概述 在空间拓扑关联挖掘中，有时需要寻找包含指定空间布 局关系的拓扑关联规则，即挖掘带空间布局约束的拓扑关联 规则。目前空间关联规则挖掘方法主要有基于聚类的图层覆 盖方法、基于空间事务的挖掘方法和无事务的空间挖掘方法 等３种类型；基于空间事务的挖掘方法是在空间数据库中利 用空间叠加、缓冲区分析等方法发现空间目标和其他挖掘对 多层关联；故这里不考虑２个空间对象相等的情况，只研究 如表１所示的７种拓扑关系。 表１空间拓扑关系－＝进倒数对应表 象之间组成的空间谓词，然后将空间谓词按照挖掘目标组成 空间事务数据库，进行布尔型关联规则挖掘，如文献［１】；这 类算法虽能在相同空间关系模式下挖掘单一空间关联，但却 ２．１转换空间事务 根据基于空间事务的挖掘方法，在目标对象的缓冲区 内，要求其与非目标对象类之间存在唯一拓扑关系，即事务 中同类非目标对象与Ｅｌ标对象之间存在的多拓扑关系已分 不能有效地提取多空间关系模式下的多层关联，如典型的空 间拓扑关联 ；文献【４—５】提出的算法虽然能够有效地挖掘多 空间关系模式下的拓扑关联，但不能挖掘包含指定空间布局 关系的拓扑关联规则；Ｓｅｐａｒａｔｅ＿ｏ 、ＡＦＭＣＡＲ口 用于传统约束 离。转换空间事务的方法如下： 性关联规则挖掘，虽它们可以用于挖掘包含空间布局约束的 拓扑关联规则，但其却存在大量的重复候选项和冗余计算。 为此，本文提出一种基于空间布局约束的拓扑关联规则挖掘 算法ＴＡＲＭＢＳＬＣ（Ｔｏｐｏｌｏｇｙ Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅ Ｍｉｎｉｎｇ Ｂａｓｅｄ ｏｎ 输入（１）一个目标对象Ｏ，，ｍ种非目标对象类别（记为 ，＝｛‘， ，…，ｆ ｝）；（２）空间拓扑关系一二进制数对应表（见表１）， 另用（０００），表示非目标对象不在目标对象的缓冲区内；（３）一 个描述空间拓扑关系的事务 基金项目：重庆市万州区科技攻关计划基金资助项目（２０１０—２３一Ｏ１）； 重庆三峡学院科研基金资助项目（１ｌＺＤ．１８） Ｓｐａｔｉａｌ Ｌａｙｏｕｔ Ｃｏｎｓｔｒａｉｎｔ），该算法能够有效挖掘包含指定空 间布局关系的拓扑关联规则。 ２基于空间布局约束的拓扑关联规则挖掘 空间拓扑关联是多空间关系模式下最复杂、最典型的空 作者简介：方［￣１Ｊ（１９７８－－），男，副教授、硕士，主研方向：数据挖 Ｅ－ｍａｉｌ：ｃｑｗｚｊｓｊｆｇ＠１６３．ｃｏｒｎ 间关联，本文将采用基于空间事务的挖掘方法，以空间拓扑 关联为例，介绍多空间关系模式下挖掘包含空间布局约束的 掘，数据库技术，地理信息系统 收稿刚啊：２０１１—０４—１１ 第３７卷第１８期 方刚：基于空间布局约束的拓扑关联规则挖掘 ３９ 输出一个整数 实现过程：先将非目标对象类按序排列；然后根据表１ 将空间事务的拓扑关系转为二进制数；即若目标对象 与非 目标对象Ⅳ丁，（其类别为ｉｋ，即Ⅳ ∈ ）之间存在表１中的某 种拓扑关系，就将其转为相应的二进制数；最后把所有的这 些二进制数按非目标对象类的顺序，排列构成二进制数，并 将其转为整数。 举例：设非目标对象类别的集合 ＝ｆ ｉ。，ｉ２，ｉ３，ｉ４｝，确定 类别顺序为｛４，３，２，１ Ｊ；设空间事务如图１所示，其中，实线 表示空间对象，虚线表示缓冲区：目标对象０，和非目标对象 Ⅳ （Ⅳ ∈ｉ２）交叠，相接非目标对象Ⅳ （Ⅳ ∈ｉ３），其包 含非目标对象Ⅳ （Ⅳ ∈ｉ４），非目标对象Ⅳ （ＮＬ∈‘）不 在目标对象０ｒ的缓冲区内。其对应的空间谓词为 ｛ｏｖｅｒｌａｐ（ ，ｉ，），ｔｏｕｃｈ（ ，ｉ３），ｃｏｎｔａｉｎ（Ｄｒ，ｆ４）｝，按类别顺序排 成二进制数（ｏｏｏ，０ｌ１，０１０，１０１）２＝２１３。 Ｏｔ 图１ 空问事务表示的空问拓扑关系 ２．２相关定义及性质 设空间目标对象为 （ｔ＝ｌ，２，…，ｎ），即是 个用于研究的 空间对象；除去空间目标对象以外的其他挖掘对象称为非目 标对象，设其所属的空间对象类别为ｉｋ（ｋ＝ｌ，２，…，ｍ），即为空 问关联挖掘的对象。 定义１权值向量，记为ｗ ，定义权值向量ＷＶ＝（２２，２ ， ２。１。 定义２类权值向量，记为ＣＷＶ，若非类别序号为ｋ，则 ＣＷＶ＝２ 一“．Ｗ１，。 定义３向量权位值，记为 ，是个整数，一个ｎ维向 量 的权位值 ’，（’，）＝２”一１。 定义４空间事务长度，记为ＳＴＬ，是个整数；其为目标 对象的缓冲区内包含非目标对象的类别个数。 举例：设空间事务ＳＴ＝｛ｉｎｓｉｄｅ（Ｄｌ，‘），ｄｉｓｊｏｉｎｔ（Ｏｌ，ｉ３）， ｔｏｕｃｈ（Ｏｌ，ｉ４），ｏｖｅｒｌａｐ（Ｏ１，ｉ５）｝，其对应的二进制数ｐ＝（１１１，０００， ００１，０１０，０１１）２，其包含非目标的类别数为４，即｛ｉ ，ｉ３，ｉ４， ｝， 于是ＳＴＬ（ＳＴ）＝ＳＴＬ（ｐ）＝４。 定义５空间事务对应整数的集合关系，空间事务 的 整数为 ，事务 的整数为 ，若 ，就记 ， 且记 为 的子集，记 为ｔ２＂的超集。 举例：设非目标对象类的集合，＿｛‘，ｆ’，ｆ１，ｆ４，ｆ ）， ＝｛ｔｏｕｃｈ（Ｏ，ｉ２），ｉｎｓｉｄｅ（Ｏ，ｉ３），ｏｖｅｒｌａｐ（Ｏ，ｉ５）），其得到二进制 数为（０００，０１０，１１１，０００，０ｌ１），，对应的整数为１ ４７５； ＝｛ｉｎｓｉｄｅ （Ｏ，‘），ｏｖｅｒｌａｐ（Ｏ，‘）｝，其得到二进制数为（０００，０００，１１１，０００， ０ｌ１）２，对应的整数为４５Ｉ；很明显 ３ ，则４５１ ３１４７５。 定义６空间布局约束，记为ＳＬＣ，是指定的空间布局条 件，其包含一个或多个空间关系，但空间关系中不能包含所 有空间类别。 定义７包含空间布局约束的拓扑关联规则，就是指从空 间数据库中挖掘包含空间布局约束的拓扑关联规则。其支持 度和置信度的定义与传统空间关联规则挖掘类似。 性质用于表示ｍ个拓扑关系的二进制数Ｐ和ｑ，Ｐ对应 的空间事务为 ，ｑ对应的空间事务为 ， ｓＬ的充 要条件是ｐＡｑ＝ｐ且ＳＴＬ（ｑＡ（ ））＝ 儿（ｑ）一ＳＴＬ（ｐ）。 推论１对ｍ位二进制数Ｐ、ｑ，Ｐ对应的整数为 ；ｑ对 应的整数为 ，如果Ｐ八ｑ＝ｐ，那么 ≤ 。 推论２空间事务 对应的整数为 ；空间事务 ｒ，ｑ对 应的整数为 ，如果 ＜ ，那么 ｓＬ。 ２．３产生空间拓扑候选频繁项的方法 如果用传统约束性关联规则算法Ｓｅｐａｒａｔｅ［６１挖掘包含空 间布局约束的拓扑关联规则，其产生候选频繁项的原理是： 任何包含空间布局约束的某频繁（ １）一项目集，至少存在 ２个具有相同（七一１）项的包含空间布局约束的频繁 一项子集。 用２种方式产生：一是主要利用连接函数产生，即任意２个 包含空问布局约束的具有（ 一１）个共同项的 一项目集连接，生 成一个包含空间布局约束的候选（ １）一项目集；二是将包含 空间布局约束的（ｋ一１）一项目集与频繁１一项目集进行一项扩展 产生。该算法产生的频繁项目集长度是递增的，但当频繁项 所含空间对象个数增多时，算法将会产生大量的重复候选项 和冗余计算，其效率会受到影响。 如果用算法ＡＦＭＣＡＲ 挖掘包含空间布局约束的拓扑 关联规则，其产生候选项的方法是从候选数字区问 的最大 值开始，用数值递减的方式产生候选；但在产生的候选数字 中有不包含空间布局约束的候选项，所以其存在冗余计算， 制约了算法效率的提高。 根据２．Ｉ节和２．２节可知，如果用ＡＦＭＣＡＲ算法挖掘多 空间模式下的拓扑关联，从候选数字区间产生的数字中不包 含空间布局约束的数目会增加，算法效率会更差；所以本算 法用空间布局约束重构非目标空间对象类的权值向量，用重 构权位值递减构建候选频繁项，克服其存在的不足。具体过 程如下： 设有ｍ种非目标对象类，记为，＝｛ｉ ，ｉ ．－，‘｝，其排序 为｛ｍ，ｍ一１，…，１｝；将空间布局约束转换成数值Ｉｎｔ（ＳＬＣ），非目 标对象中不包含空间布局约束类的类有ｓ（１≤ ＜ ）种，则其类 别序号为｛ｋｌ，ｋ，，…，ｋｓ）。 （１）重构非目标对象中不包含空间布局约束类的类权值 向量，即删除空间布局约束的类，重新按原序排列类权值向 量，记为向量Ｒ＝（２３（ｋ，－１）ＷＶ，２３（ｋ２－１）ＷＶ，…，２３（ｋ￣－１）ＷＶ），则 ｖｗｖ（Ｒ）＝２ 一１。 （２）确定产生候选频繁项的数字区间，即Ｅ＝［１，ＶＷＶ（Ｒ）］。 （３）设ＸＥ Ｅ，Ｘｏ＝２ 一１，记为向量 （ ）＝（ ｌ’ｂ２，…，ｂ３ ）‘ ∈［０，１］，其分量即为Ｘ的二进制形式；用递减Ｘ来产生候选 频繁项ｃ ，即ｃ ＝Ｉｎｔ（ＳＬＣ）十Ｒ・ｙ（ ）。 举例：设空间非目标对象类有４种，－｛Ａ，Ｂ，Ｃ，Ｄ｝，其类 别序号为｛４，３，２，１），若指定的空间布局约束ＳＬＣ为 ｛ｏｖｅｒｌａｐ（ ，Ｂ），ｔｏｕｃｈ（Ｄｒ，Ｄ）｝，其对应的二进制数为 （００ｏ，０１１，０００，０１０），，Ｉｎｔ（ＳＬＣ）＝１９４，空间布局约束的对象类为 ｛曰，Ｄ），’则产生过程如下： （１）非目标对象中不包含空间布局约束类的类权值向量 有Ｃｗ ＝２ －ｗＶ和ｃｗ ＝２ ＷＶ，由定义１知道 ＷＶ＝（２ ，２ ，２ｏ），故重构排序得到Ｒ＝（Ｃｗ ，ｃｗｖ２）＝ （２３×（ ”．ＷＶ，２３￣（２－”．ＷＶ）＝（２”，２ ，２ ，２ ，２ ，２３）。 （２）ＶＷＶ（Ｒ）＝２ 一１＝２６＿１＝６３，确定产生候选频繁项 计算机工程 ２０１１年９月２０日 的数字区间Ｅ＝【１， ｗ Ｒ）】，即【ｌ，６３］。 （３）候选频繁项的产生过程： ＸＩ＝６３，即Ｖ（ｘＩ）＝（１，１，１，１，１，１） ，则有： Ｃ ＝ｌｎｔ（ＳＬＣ）＋ ・ （ １）＝ １９４＋２ ＋２ ‘ ＋２ ＋２ ＋２ ＋２ ＝３ ８３４ Ｘ２＝６２，即Ｖ（ｘＯ＝（Ｌ１，１，１，１，０） ，则有： Ｃ ＝ｌｎｔ（ＳＬＣ）＋ ・ｙ（ ，）＝ １９４＋２“＋２‘ ’＋２ ＋２ ＋２ ＝３ ８２６ Ｘ３＝６１，即Ｖ（ｘ３）＝（１，１，１，１，０，１） ，则有： Ｃ ＝Ｉｎｔ（ＳＬＣ）＋Ｒ－Ｖ（ ）＝ １９４＋２”＋２ 。＋２ ＋２ ＋２ ＝３ ８１８ ６３＝１，即Ｖ（ｘ６ ）＝（０，０，０，０，０，１） ，则有： Ｉｎｔ（ＳＬＣ）＋Ｒ・Ｖ（ｘ６３）：１９４＋２ ＝２０２ ２．４计算支持效的方法 多数空间关联规则挖掘算法在计算支持数时，需要判断 空间事务是否支持候选频繁项。根据２．２节的性质，算法首 先用候选频繁项与空间事务对应的整数进行“与”运算，满 足条件后再判断长度条件，若２个条件都满足才能判断出事 ｌ圣蓝靶心 务之间的支持关系；另外计算时只需扫描数据库中对应整数 ４ ２ Ｏ ８ ６ ４ ２ 大于或等于候选项整数的所有空间拓扑关系事务。∞０ ∞Ｏ ∞Ｏ ∞Ｏ ∞Ｏ ∞Ｏ Ｏ ∞ Ｏ ３算法的性能分析及实验比较 ３．１算法的正确性和完备性分析 根据２．２节性质，证明了挖掘空间拓扑关联的正确性， 即空间事务之间的关系是可以正确判断的，保证了计算支持 数的正确性；另外，若空间非目标对象类别个数为ｍ，空间 布局约束中的非目标对象类的个数为ｔ（１≤ｔ＜ｍ），则包含空间 布局约束的候选项个数最多有２ “一１个，而根据２．３节产 生候选频繁项的方法可以知道，产生候选频繁项的数字范围 Ｅ为 １ ２ Ｊ＿１】，所以不会遗漏频繁项，算法具有完备性。 ３．２算法的性能分析 （１）时间复杂度分析 设数据库中不重复事务数为ｎ（ｎ≤２ ），空间非目标对 象类别个数为ｍ，空间布局约束中的非目标对象类的个数为 ２３￣１ 一Ｉ ｔ（１≤ｆ＜ ），则时间复杂度表示为：Ｔ：∑ｋ＋２ ’一１。 ｋ＝ｌ （２）空问复杂度分析 算法将空间事务转换为整数进行压缩存储，其空间复杂 度可表示为Ｏ（ｓ．ｎｘＭ），Ｍ为最大项目集，Ｓ是一个与支持度 和空间布局约束类有关的参数。 ３．３实验结果比较 用现有约束性关联规则挖掘算法Ｓｅｐａｒａｔｅ和ＡＦＭＣＡＲ， 与提出的ＴＡＲＭＢＳＬＣ进行模拟实验比较。 测试数据：总数为７ｌ ６５０，有４ ０９５个不重复事务数， 其对应的整数为１～４ ０９５，对事务的重复个数按“５”和“３０” 交替出现，即４ ０９５有５个，４ ０９４有３０个，４ ０９３有５个， ４ ０９２有３０个，…，空间对象类别数为４。空间布局约束对 应的整数为３和９，其谓词分别表示为ｏｖｅｒｌａｐ（Ｏ，Ｄ）和 ｛ｄｉｓｊｏｉｎｔ（Ｏ，Ｃ），ｄｉｓｊｏｉｎｔ（Ｏ，Ｄ）Ｊ，Ｏ为目标对象类，Ｃ与Ｄ分 别为第３个和第４个非目标对象类别。 实验环境：Ｉｎｔｅｌ（Ｒ）Ｃｅｌｅｒｏｎ（Ｒ）Ｍ ＣＰＵ ４２０＠１．６０ ＧＨｚ， １．２４ ＧＢ的内存，操作系统为Ｗｉｎｄｏｗｓ ＸＰ Ｐｒｏｆｅｓｓｉｏｎａｌ，在 Ｖｉｓｕａｌ Ｃ＃２００５．ＮＥＴ开发平台上实现Ｓｅｐａｒａｔｅ、ＡＦＭＣＡＲ和 ＴＡＲＭＢＳＬＣ ３个算法。 在上述实验环境和挖掘数据库下，用Ｓｅｐａｒａｔｅ、ＡＦＭＣＡＲ 和ＴＡＲＭＢＳＬＣ ３个算法挖掘频繁拓扑关联项目集，实现算 法效率的比较；在实验中通过２种空间布局约束条件，比较 算法随着支持度减少的运行时间；每种支持度下的运行时间 是多次测试结果的平均值。 在空间布局约束为ｏｖｅｒｌａｐ（Ｏ，Ｄ）下，算法运行时间随支 持度的变化比较情况如图２所示，在空间布局约束为 ｛ｄｉｓｊｏｉｎｔ（Ｏ，Ｃ），ｄｉｓｊｏｉｎｔ（Ｏ，Ｄ）｝下，运行时间随支持度的变化 比较情况如图３所示。 ０ ４Ｉ９ ０ ２７９ ０ １４Ｏ ０ ０７０ ０ ０２８ ０ ０ｌ４ ０ ００７ ０ ００４ 支持度Ｈ％） （ａ）Ｓｅｐａｒａｔｅ和ＴＡＲＭＢＳＬＣ（约束整数为３） 虬ｎ宣誓 ｉ｝ 瑚 ㈨∞。 ４ ２ ０ ８ ６ ４ ２ ∞∞∞∞∞∞∞ ０ ０ Ｏ ０ ０ Ｏ Ｏ ０ ０４１ ９ ０ ２７９ ０ １４０ ００７０ ０ ０２８ ０ ０ｌ４ ０ ００７ ０ ００４ 支持度／（％） （ｂ）ＡＦＭＣＡＲ和ＴＡＲＭＢＳＬＣ（约束整数为３） 图２不同算法的运行时间比较１ ０ ４１９ ０ ２７９ ０ １４０ ００７０ ０ ０２８ ０ ０１４ ０００７ ０ ００４ 支持度 ％） （ａ）Ｓｅｐａｒａｔｅ和ＴＡＲＭＢＳＬＣ（约束整数为９） ０ ４Ｉ ９ ０ ２７９ ０ １４０ ０ ０７０ ０ ０２８ ０ ０１４ ０ ００７ ０ ００４ 支持度／（％） （ｂ）ＡＦＭＣＡＲ和ＴＡＲＭＢＳＬＣ（约束整数为９） 图３不同算法的运行时间比较２ 从实验结果可知，在挖掘空间布局约束的拓扑关联规则 时，虽然Ｓｅｐａｒａｔｅ算法适合挖掘支持度较大的情况，此时频 繁拓扑关联项目集的平均长度较短，但其还是没有ＴＡＲＭＢ ＳＬＣ算法快速；虽ＡＦＭＣＡＲ算法适合挖掘支持度较小的情 况，此时频繁拓扑关联项目集的平均长度较长，但其还是没 有Ｔ－ＡＲＭＢＳＬＣ算法高效。 （下转第４３页） 姗第３７卷第１８期 骆挺，钟才明，陈辉：基于完全子图的社区发现算法 ４３ Ｚａｒｃｈａｒｙ Ｋａｒａｔｅ网络是美国一所大学中空手道俱乐部成员间 的相互社会关系网络。在调查过程中，该俱乐部的主管和校 长产生了矛盾，结果该俱乐部分裂成２个分别以主管和校长 为核心的小俱乐部。本文算法执行该网络能自动发现 ２个 社区，并且结果跟实际一致，准确率达到１００％，如图７所示。 ２ｓ＇，Ａ ．Ｖ 二 ： 事 图８本文算法对Ｄｏｌｐｈｉｎ网络的聚类结果 ４结束语 ＼ 本文提出一种基于完全子图的社区发现算法，利用节点 社区归属度来决定个别节点的归属。该算法不需要任何参数 的设置，可以自动识别社区数目。实验结果证明，该算法能 Ｉ６够准确识别网络中的社区，具有一定的使用价值。今后的工 图７本文算法对Ｚａｃｈａｒｙ网络的聚类结果 作将研究社区与社区边界的问题，因为很多实际网络中的某 Ｋｅｒｎｉｇｈａｎ—Ｌｉｎ算法得到的结果也跟实际结果一样，但是 些节点不仅属于一个社区。 该算法必须提前知道２个社区的大小分别是１６和１８。该算 参考文献 法很难应用于实际网络。ＧＮ算法，谱二分方法的结果为节 ［１］Ｓａｎｔｏ Ｅ Ｃｏｍｍｕｎｉｔｙ Ｄｅｔｅｃｔｉｏｎ ｉｎ Ｇｒａｐｈｓ［ＥＢ／ＯＬ］．（２０１０一叭一２５）． 点３被误分。此实验证明本算法相比其他算法可以更有效发 ｈｔｔｐ：／／ａｒｘｉｖ．ｏｒｇ／ａｂｓ／０９０６．０６１２． 现网络社区内在结构，并且不用设定任何的参数。 ［２］Ｋｅｒｎｉｇｈａｎ Ｂ Ｗ．Ａｎ Ｅｆｆｉｃｉｅｎｔ Ｈｅｕｒｉｓｔｉｃ Ｐｒｏｃｅｄｕｒｅ ｆｏｒ Ｐａｒｔｉｔｉｏｎｉｎｇ 海豚关系网也是社会网分析中常用的一个真实网络，每 Ｇｒａｐｈｓ［Ｊ］．Ｂｅｌｌ Ｓｙｓｔｅｍ Ｔｅｃｈｎｉｃａｌ Ｊｏｕｒｎａｌ，１９７０，４９（１）：２９１—３０８． 个节点代表一个海豚，边表示２个海豚之间接触频繁。该网 ［３】Ｇｉｒｖａｎ Ｍ，Ｎｅｗｍａｎ Ｍ Ｅ Ｊ．Ｃｏｍｍｕｎｉｔｙ Ｓｔｒｕｃｔｕｒｅ ｉｎ Ｓｏｃｉａｌ ａｎｄ 络共有６２个节点，１５９条边。实际的网络有４１个较大的海 Ｂｉｏｌｏｇｉｃａｌ Ｎｅｔｗｏｒｋｓ［ＥＢ／ＯＬ］．（２００２—０４—０６）．ｈｔｔｐ：／／ｗｗｗ．ｐｎａｓ．ｏｒｇ／ 豚家族，２１个较小的海豚家族。 ｃｏｎｔｅｎｔ／９９／１２／７８２１．ｆｕ１Ｉ＿ 本文算法把该网络分成４个社区，其中一个社区 ［４］Ｎｅｗｍａｎ Ｍ Ｅ Ｊ，Ｇｉｒｖａｎ Ｍ．Ｆｉｎｄｉｎｇ ａｎｄ Ｅｖａｌｕ￣ｉｎｇ Ｃｏｍｍｕｎｉｔｙ （Ｄｉａｍｏｎｄ节点）跟实际２１个海豚的社区完全一样。而另外 Ｓｔｒｕｃｔｕｒｅ ｉｎ Ｎｅｔｗｏｒｋｓ［ＥＢ／ＯＬ］．（２００４—０８－１１１．ｈｔｔｐ：／／ａｒｘｉｖ．ｏｒｇ／ａｂｓ／ ３个社区预示着将来４１个较大海豚家族有可能分裂成３个家 ｃｏｎｄ．ｍａｆｆ０３０８２１７． 族。对于Ｋｅｒｎｉｇｈａｎ—Ｌｉｎ和ＧＮ算法，总有一个节点被误分。 ［５］ 王 林，戴冠中．一种新的评价社区结构的模块度研究［Ｊｌ ＿实验再次证明本算法的正确性，并且该算法还具有一定的预 计算机工程，２０１０，３６（１６）：２２７—２２９． 测性，如图８所示。 编辑陈文 （上接第４０页） ４结束语 ［３］ 汤小斌，方 刚．一种用于空间横向挖掘的拓扑关联规则算 现有空间挖掘算法不能够有效地提取包含空间布局约束 法［Ｊ】．计算机工程与应用，２０１０，４６（１）：１０９—１１１． 的拓扑关联规则，如果用传统约束关联规则算法进行挖掘， ［４］ 罗爱萍．空间跨层关联规则挖掘算法研究Ⅲ．西南师范大学学 会出现重复候选项和冗余计算的问题，因此，本文提出一种 报：自然科学版，２００９，３４（４）：１－５． 基于空间布局约束的拓扑关联规则挖掘算法，实验结果验证 ［５】 方 刚，魏祖宽，刘雨露，等．一种挖掘空间拓扑关联的有效 了该算法的有效性。 算法［Ｊ１＿计算机工程与设计，２０１０，３１（６）：１２６７—１２７０． 参考文献 ［６］邵峰晶，于忠清，王金龙，等．数据挖掘原理与算法【Ｍ］．北京： ［１］ 刘雨露．基于序号索引的空间关联规则挖掘算法［Ｊ１．计算机工 科学出版社，２００９． 程，２０１０，３６（１６）：５４—５６． ［７］方 刚．一种快速挖掘约束性关联规则的算法【ＪＪ．计算机应用 ［２］ 熊 江，方 刚，刘雨露，等．空问拓扑关联的双向挖掘研 与软件，２００９，２６（８）：２６８—２７０． 究［Ｊ］＿计算机工程与应用，２００９，４５（２２）：１２６—１２８． 编辑陈文
