藕藉
应 用 方 法 论
１ ７ ３
一
种 改进 的ＤＢＳ ＡＮ聚 类融合算法及应 用 Ｃ
黄衍 标 ，魏育 华
（ 广州华立科技 职业学 院，广 东广州 ５ １ ２ １ ３ ５）
摘 要 Ｄ Ｓ Ａ 高密度 聚类 是数据挖 掘 中聚类算 法里常用 的一 种分析 方法 ，它能找 出样本 比较 密集 的部 分并概 括 ｍ样 本相对 比较集 中的 ＢＣ Ｎ 类 。本文通过 分析Ｄ Ｓ Ａ 算法 特点并对 其缺陷加 以改进运 用于Ｒ ｈ ｃ ｐ ＢＣ Ｎ ｏ ｏ ｕ 中型组 机器人数 据融合 系统 ，实验 结果表 明运用Ｄ ｓ Ａ 算 法可以 Ｂｃ Ｎ 大 幅度提高机 器人 目标 定位 的准确性 。 关 键 词 聚类融合 ；Ｄ Ｓ Ａ Ｂ Ｃ Ｎ；密度 ；Ｒ ｈｃ ｐ ｏｏ ｕ 中型组数据融 合 中 图分 类 号 Ｔ Ｐ 文献 标 识码 Ａ 文 章编 号 １７— ６ １（ １）７— １３Ｏ ６ ３９ ７一 ０ ０２ ０７一 １ ２ １
２１ 数 据 结 构 的 聚类算法 － 邻接表建 立完成后 ，就要开始进行聚类运算了。算法大致 的工作流 程如下 ： １ 初 始化一些参数 ，其中领 域半径 值Ｅ Ｓ ） Ｐ 和门限值 Ｍ ｎｔ￣机器人 ｉ ｓ ｐｌ 系统 的比赛实际情况确定 ，以４ ｓ Ｒ ｂＣ ｐ Ｖ ４ ｏ ｏ ｕ 中型足球机器人 比赛系统来 说 ，本文选领域半径值Ｅ Ｓ＝０ ｍ，Ｍｉ ｔ＝２ Ｐ ． ３ ｎ ｓ ，聚类数Ｋ＝ 。 ｐ ０ ２）将对象集 Ｆ 中所有对象插 入到邻接 表 ，逐个扫描邻 接表基 表中 的对象 ，判断其是否已经被 聚类过 了 （ 通过判断ｕｅｔ ￣实现 ），如果 ｓｄａ ｇ 是 ，则跳过这一对象 ，否则开始下一步 。 ３） 断其是否为核心点 ，只有 核心点才能发起一次聚类活动 ，是 判 则Ｋ＝Ｋ＋１ 并开始步骤４ 。若此点非核心点则将其标记并跳过这一对象 ， 留待以后 的收尾处理 。 ４ 对这一点开始聚类 ，ｉ ： 。然后逐一检索该基表元素后链 接的 ） ｄ Ｋ 结点链 ，从而查 找出此点邻域 内的所有点 ，并对这些点进行判断。设其 邻域内的点为ｂ ，情况 １ 已经被聚类 过了 ， ：ｂ 则不对ｂ 进行任何处理 ；情 况２ 未被聚类过且是核心点 ，则将其作为新种子压栈 ，以待后面对其 ：ｈ 进行递归地聚类处理 ；情况３ 未被聚类 过且不是核心点 ，则将类 号填 ：ｂ 入ｂ ｄ 的ｉ 变量中，说 明ｂ 已经被聚类为ｉ ｄ 了。不管是哪种情况 ，都将ｂ 点标 识为已经聚类过 ，以免 以后进行不必要 的重复处理 。 ５）从种子栈 中取 出一个元素 ，递归地对其进行聚类 。类号ｉ不变， ｄ 因为这还是属 于原来的类。如此递归 ，直 到种子栈为空为止。这 时，标 明类号为ｉ的聚类活动完成。 ｄ ６ 判断Ｋ ） 的值 ，当Ｋ 不大于４ 时返回步骤２ 再次扫描邻接 表基表 中的 元素。 ７）归 一处理 ：将遗 留点 （ 例如不 属于任何类的非核心点 ）进行噪 声点处理，对各类 中的节点进行归一化 ，如多个点进行加权平均运算变 成一个点 。
聚类是一种重要的数据分析技术 。聚类分析作为统计学的一个分 支 已经被广泛研究 了许多年。而且 ，聚类分析也 已经广泛地应用 到诸 多领 域 中，包括人 ＿智能 、 ｒ 模式识别 、 数据分析 、图像处理 、推荐 系统 以及 市场研究等领域 。通过聚类 ，人们 能够识别密集 的和稀疏的区域 ，因而 发现全局 的分布模式 ，以及 数据属性之 间有趣 的相互关系。本 文针对 目 前Ｄ Ｓ Ａ 算法的特点及缺陷将之稍作改变并实现其算法步骤 ，然后放 ＢＣ Ｎ 到具体应用中加 以实验测试 。
２ 算 法 改进 及 实现
本 文以典型的多移动机器人系统Ｒ ｂ Ｃ ｐ ｏ ｏ ｕ ￣型足球 机器人 比赛系统 为应 用实例 ，由大量 的实验数据统计结果表明 ，比赛 系统 中各机器人返 回的 目标 定位数据 总是以呈正态 分布形式 出现在实 际位 置的周 同。因 此 ，本文 以Ｒ ｈｃ ｐ ｎ ｏ ｕ 中型足球机器人 比赛 系统的 目标定 位作为改进后的 Ｄ Ｓ Ａ 算法的应用环境 。 ＢＣ Ｎ 机器人需要辨别的 目标如球 、场上机器 人等 的位置都是 以二维坐标 点的方式表示 的。在写一个 比较完整的程序之前 ， 通常要先规划好程序 的数据结构及算法。
ｌ ｋ ｏｅ ＊ｅｔ， ｉ Ｎ ｄ ｌ ｎｘ；用于链接下一个点 ｎ ／
）ｎ Ｎ ｄ； ｌ ｋ ｏｅ ｉ
１ Ｂ Ｃ Ｎ算 法简 介及 特点 Ｄ Ｓ Ａ
Ｄ Ｓ Ａ 算法利用类 的高密度连通性 ，快速发现任意形状的类 。其 ＢＣ Ｎ 基本思想是 ：对于一个类 中的每个对象 ，在其给定半径的领域 中包含 的 对象不能少于某一给定 的最小数 目。为了发现 一个类 ，Ｄ Ｓ ＡＮ Ｂ Ｃ 先从对 象集Ｆ 中找到任意一对象Ｐ 并查找Ｆ ， 中关于半径Ｅ Ｓ Ｐ 和最小对象数Ｍ ｎ ｔ ｉ ｓ ｐ 的从Ｐ 密度直达的所有对象。若Ｐ 是核心对 象，也就是说半径为Ｅ Ｓ 的 Ｐ 的Ｐ 领域中所包含 的对象数不小于Ｍ ｎ￣ ｉ ，则通过区域查询 （ｅｉ ｅ ） ｐ ｒ ｏ ｑ ｒ 可 ｇｎ ｕ ｙ 以找到一个关 于Ｅ ｓ ｎ 的类 ，即集合ｃ Ｐ 和Ｍｉ 。如果Ｐ 是一个边界点，则半 径为Ｅ Ｓ 的领域 中所包含的对象ｉ ＝ Ｍ ｎｔ， 被暂时标注为噪声点 ， Ｐ 的Ｐ ｂｆ ｉ ｓ Ｐ ： ｐ 然后 继续循环处理Ｆ 中下一个对象直到找出所有类。 Ｄ Ｓ Ａ 算法是一种基 于密度 的空间数据聚类方法 ，该算法的显著 ＢＣ Ｎ 优点是 聚类速度快 ，且能够有 效处理 噪声 点和发现 任意形状 的空间聚 类。但 由于它在进行 聚类时使用 了一个全局性的表征密度 的参数 ，因此 也具有 比较明显的弱点 ：一是要求人为确定参数 ；二是 当空间聚类密度 不均匀 ，聚类间距离相差很大时 ，聚类质量将会受 到影响。