第３８卷 第１８期 计算机工程 ２０１２年９月 Ｖ０ｌ＿３８ ＮＯ．１８ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ Ｓｅｐｔｅｍｂｅｒ ２０１２ ・人工智能及识别技术・ 文章缩号ｔ １００ｏ—＿３４２８（２０１２）１ ８．＿＿０ｌ５８—＿０４ 文献标识码ｔ Ａ 中圈分类号ｔ ＴＰ３０１．６ 基于多主体技术和数学形态学的空间聚类算法 路红 ，陈立潮 ，潘理虎 ，一，闰慧敏 ，黄河清 （１．太原科技大学计算机科学与技术学院，太原０３００２４；２．中国科学院地理科学与资源研究所，北京１００１０１） 摘要：空间数据复杂多变、数据量庞大，且数据分析较为困难。为解决该问题，提出一种基于多主体技术和数学形态学灰度形态运算的 聚类算法。将结构元素作为智能个体，Ａｇｅｎｔ根据其所处空间位置环境的Ｍｏｏｒｅ Ｎｅｉｇｈｂｏｒｈｏｏｄ值或ＶＮ Ｎｅｉｇｈｂｏｒｈｏｏｄ值，采用ＯＣＣ算子 自主选择做灰度膨胀或腐蚀运算。实验结果表明，该算法具有较好的准确性、可靠性和灵活性，能对任意聚类形状进行快速聚类。 关黼：Ａｇｅｎｔ技术；数学形态学；灰度膨胀；结构元素；灰度腐蚀；空间聚类算法 Ｓｐａｔｉａｌ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ０ｎ Ｍｕｌｔｉ－ａｇｅｎｔ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｍａｔｈｅｍａｔｉｃ Ｍｏｒｐｈｏｌｏｇｙ ＬＵ Ｈｏｎｇ ，ＣＨＥＮ Ｌｉ．ｃｈａｏ ，ＰＡＮ Ｌｉ．ｈｕ ， ，ＹＡＮ Ｈｕｉ．ｍｉｎ ，ＨＵＡＮＧ Ｈｅ－ｑｉｎｇ （１．Ｓｃｈｏｏｌ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｔａｉｙｕａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＳｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｔａｉｙｕａｎ ０３００２４，Ｃｈｉｎａ； ２．Ｉｎｓｔｉｔｕｔｅ ｏｆＧｅｏｇｒａｐｈｉｃ Ｓｃｉｅｎｃｅｓ ｎａｄ Ｎａｔｕｒａｌ Ｒｅｓｏｕｒｃｅｓ Ｒｅｓｅａｒｃｈ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １００１Ｏ１，ＣｈｉＩｌａ） ［Ａｂｓｔｒａｃｔｌ Ｔｈｅ ｓｐａｔｉａｌ ｄａｔａ ｉｓ ｃｏｍｐｌｅｘ，ｃｈａｎｇｅｆｕｌ，ａｎｄ ｍａｓｓ，ＳＯ ｔｈｅ ｗｏｒｋ ｏｆ ｓｐａｔｉａｌ ｄａｔａ ａｎａｌｙｓｉｓ ｉｓ ｏｎｅｒｏｕｓ，ａ ｓｐａｔｉａｌ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｈｔｍ ｂａｓｅｄ ｏｎ ｍｕｌｔｉ—ａｇｅｎｔ ｔｅｃｈｎｏｌｏｇｙ ａｎｄ ｍａｔｈｅｍａｔｉｃ ｍｏｒｐｈｏｌｏｇｙ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｓｏｌｖｅ ｔｈｉｓ ｐｒｏｂｌｅｍ．Ｔｈｅ ｓｔｒｕｃｔｕｒａｌ ｅｌｅｍｅｎｔ ｏｆ ｈｔｅ ｍａｔｈｅｍａｔｉｃ ｍｏｒｐｈｏｌｏｇｙ ｉｓ ｓｅｌｅｃｔｅｄ ａｓ Ａｇｅｎｔ．Ｂａｓｅｄ ｏｎ ｔｈｅ ｖａｌｕｅｓ ｏｆ Ｍｏｏｒｅ Ｎｅｉｇｈｂｏｒｈｏｏｄ ｏｒ ＶＮ Ｎｅｉｇｈｂｏｒｈｏｏｄ ｉｎ ｔｈｅ ｅｎｖｉｒｏｎｍｅｎｔ ｏｆ ｔｈｅｉｒ ｓｐａｔｉａｌ ｌｏｃａｔｉｏｎ，ｔｈｅ Ａｇｅｎｔｓ ａｕｔｏｎｏｍｏｕｓｌｙ ｃｈｏｏｓｅ ＯＣＣ ｏｐｅｒａｔｏｒ ｔｏ ｄｏ ｇｒａｙ ｄｉｌａｔｉｏｎ ｏｒ ｅｒｏｓｉｏｎ ｏｐｅｒａｔｉｏｎ ｔｏ ｉｍｐｌｅｍｅｎｔ ｓｐａｔｉａｌ ｃｌｕｓｔｅｒｉｎｇ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｉｓ ａｌｇｏｒｉｈｔｍ ｈａｓ ｓｉｇｎｉｉｆｃａｎｔ ａｃｃｕｒａｃｙ，ｒｅｌｉａｂｉｌｉｔｙ，ｆｌｅｘｉｂｉｌｉｔｙ，ａｎｄ Ｃａｎ ｒａｐｉｄｌｙ ｃｌｕｓｔｅｒ ａｎｙ ｓｈａｐｅｓ ｏｆｃｌｕｓｔｅｒｉｎｇ． ［Ｋｅｙ ｗｏｒｄｓｌ Ａｇｅｎｔ ｔｅｃｈｎｏｌｏｇｙ；ｍａｔｈｅｍａｔｉｃ ｍｏｒｐｈｏｌｏｇｙ；ｇｒａｙ ｄｉｌａｔｉｏｎ；ｓｔｒｕｃｔｕｒｅ ｅｌｅｍｅｎｔ；ｇｒａｙ ｅｒｏｓｉｏｎ；ｓｐａｔｉａｌ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｈｔｍ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００—３４２８．２０１２．１８．０４３ １概述 献【６－７］分别针对网络，大数据集提出基于Ａｇｅｎｔ的聚类 随着空间数据规模的越来越大、结构越来越繁杂，数 方法。 据挖掘面临艰巨的挑战。聚类分析是数据挖掘研究领域的 无智能的主体通过合作，表现出智能行为的特性，并 重要内容之一。然而不同领域的应用对聚类算法有特殊的 且通过局部更新规则 得到启发，本文采用Ａｇｅｎｔ技术与 要求，而现有的聚类算法在灵活性、对噪声和数据输入顺 数学形态学结合的方式，提出一种空间聚类算法。以数学 序的敏感性，以及算法效率等聚类期望特征方面还不能满 形态学中的结构元素为Ａｇｅｎｔ，由Ａｇｅｎｔ选择做灰度膨胀 足类似的要求。 或腐蚀运算，同时用结构元素自带的颜色信息实现自动 基于多主体聚类的本质特征是智能体根据给定的数 聚类。 据集自动决定合适的聚类簇数。多主体聚类ＰＡＤＭＡ ２基于Ａｇｅｎｔ和数学形态学的聚类算法 （Ｐａｒａｌｌｅｌ Ｄａｔａ Ｍｉｎｉｎｇ Ａｇｅｎｔｓ）…被用来对文档按层次生成 本文采用局部探索随机行走方法，让所有Ａｇｅｎｔ独立 聚类簇。文献［２】提出的基于Ｊａｖａ和移动Ａｇｅｎｔ的分布式 进行形态学计算，从而实现分布式的数学形态学几类运 数据挖掘系统Ｐａｐｙｒｕｓ，采用对等模式根据给定的多主体 算。算法对聚类数没有要求，实验对象是数字高程图像 系统（Ｍｕｌｔｉ—ａｇｅｎｔ Ｓｙｓｔｅｍ，ＭＡＳ）策略，聚类结果在Ａｇｅｎｔ （Ｄｉｇｉｔａｌ Ｅｌｅｖａｔｉｏｎ Ｉｍａｇｅ，ＤＥＭ）。灰度形态学膨胀和腐蚀的 移动时呈现。文献【３．４］采用多主体技术，与聚类算法结合 定义如下： 实现了多主体聚类算法。文献［５］提出由聚类Ａｇｅｎｔ和聚类 设ｆｉｘ，ｙ）是输入的图像灰度函数，６ ）是给定的结构 评估Ａｇｅｎｔ组成的非监督机制的智能多主体聚类系统。文 元素，且都定义在 或Ｚ２，Ｄ，和Ｄ６分别是函数ｆｉｘ：）和 基金项目：国家自然科学基金资助项Ｎ（４１０７１３４４）；太原科技大学博士创新基金资助项Ｎ（２０１０２０３０） 作者倚介：路红（１９７５一），女，硕士研究生，主研方向：数据挖掘，人工智能；陈立潮，教授、博士；潘理虎，副教授、博士；闫慧敏， 副研究员、博士；黄河清，研究员、博士 收藕日期：２０１１－ｌ１一Ｏ９ ．Ｉ｝回日期：２０１２一叭一０４ Ｅ－ｍａｉｌ￣ｐａｎｌｙｈｏｏ＠ｓｏｈｕ．ｃｏｒｎ 第３８卷第１８期 路红，陈立潮，潘理虎，等：基于多主体技术和数学形态学的空间聚类算法 １５９ 则６ ）对 ｂ（ｘ，ｙ）的定义域， 式为： ）进行灰度膨胀的运算 为另一个聚类簇的标定值。算法框架如图２所示。 （厂０ ６）（ ，ｔ）＝ｍａｘｔ，【 —Ｘ，ｔ－ｙ）＋ｂ（ｘ，ｙ）ｌ（ｓ— ），（ｆ—Ｙ）∈ Ｄ，（ ）∈Ｄｂ｝ （１） ６ ）对ｙｆｘ，ｙ）进行灰度腐蚀的运算式为： （ ６）（ ｆ）＝ｍａｘ ｓ＋ｘ，产 ）一 ｂ（ｘ ）ｌ（ ），（ｔ＋ｙ）∈Ｄｊ（ｘ，ｙ）∈Ｄｂ｝ （２） 算法基本思想是将Ａｇｅｎｔ与结构元素结合起来，每一 个Ａｇｅｎｔ对应一个结构元素。并驱动该结构元素进行形态 学计算。在要聚类的目标图像上随机分布若干Ａｇｅｎｔ，并 把Ａｇｅｎｔ当前所处位置定为与之对应的结构元素的热点。 Ａｇｅｎｔ根据自身所处的位置用其Ｍｏｏｒｅ邻域或ＶＮ邻域的 值与给定阈值比较而后判断是做灰度膨胀运算还是灰度 腐蚀运算。在此本文提出一种新的算子一一ＯＣｃ（Ｅｌｅｍｅｎｔ Ｃｅｎｔｅｒ Ｂａｓｅｄ Ｏｐｅｒａｔｏｒ Ｕｓｉｎｇ Ｃｌａｓｓｉｉｆｃａｔｉｏｎ ａｎｄ Ｃｏｍ— ｐａｒｉｓｏｎ），结构元素如图１所示。 赶 蜀 托 咒 Ｘ７ （ａ）３ｘ３正方形 （ｂ）３×３十字形 圈１算子的结构元素 ＯＣＣ算子的思想是：选取图１（ａ）为结构元素，则把 作为结构元素的中心点，即Ａｇｅｎｔ所在空间位置， 一 的值与给定阈值比较，统计小于阈值的个数计为 ｃｏｕｎｔｌ，大于阈值的个数计为ｃｏｕｎｔ２。如果ｃｏｕｎｔｌ小于 ｃｏｕｎｔ２，则给蜀赋属于一个簇的标定值，否则赋属于另一 个簇的标定值。 如果聚类数目多于２类方法同上类推，同样用图ｌ（ｂ） 十字形结构元素应把 作为结构元素的中心点，即不论 采用什么形状的结构元素，都用其中心点作为结构元素的 热点，热点也是Ａｇｅｎｔ所在的空间位置。 ３算法描述 变结构元素为１×１大小的方格用当前热点做灰度膨 胀、腐蚀运算，并且假设：ａ为一个特定簇的标记值； 图２算法框架 本文算法根据属性值进行聚类。图像的灰度取值区间 是［０，Ｊｖ］，即ｙ（ｘ，ｙ）∈［０，Ⅳ］，Ｎ∈Ｚ，其中，ｚ是整数集合， 图像背景信息值为一９ ９９９。假设任一点到同一类中，相邻 点属性值的差小于其到其他类中任意点的属性值差，即属 于一类的目标属性值大至相同。本文算法不仅考虑空间属 性，还考虑了非空间属性，从而可以提高聚类质量。 ３．１算法描述步骤 算法的步骤如下： Ｓｔｅｐｌ输入图像并显示。 Ｓｔｅｐ２ Ａｇｅｎｔ随机分布未做过操作的空间位置。 Ｓｔｅｐ３ Ａｇｅｎｔ在当前位置用变结构元素做灰度形态学 运算：若Ａｇｅｎｔ刚好在图像的边界上，用１×１的结构元素 做灰度形态学运算，否则用３ｘ３的正方形结构元素做运 算，并显示其所属的簇。 Ｓｔｅｐ４令做过操作的Ａｇｅｎｔ消亡，并选择未做过操作 的位置上生成新的Ａｇｅｎｔ，返回到Ｓｔｅｐ３。 Ｓｔｅｐ５当没有新的Ａｇｅｎｔ生成时，聚类结束。
