双星
５５“ 神舟一号”试验飞船
１９９９ 年 １０ 月 １４ 日， 在太原 卫 星 发 射 中 心 ， 用“ 长 征 四 号 乙 ”运 载 火
补充材料： 发射“ 神舟一号”的“ 长征二号 Ｆ”， 是“ 长征”系列运载火箭
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
１９９６ 年 ６ 月 １２ 日， 在太原卫星发射中心， 用“ 长征二号丙改”运载火 箭成功地将两颗“ 铱星”送入预定轨道。此次发射是“ 长征”系列运载火箭 的第 ５７ 次飞行， 也是自 １９９６ 年 １０ 月以来“， 长征”系列运载火箭连续 １５ 次成功发射， 又是中方履行“ 铱星”发射合同的第三次补网铱星成功发射 服 务 。中 国 航 天 界 在 参 加 这 种 世 界 多 个 国 家 和 地 区 合 作 的 全 球 卫 星 个 人 通 信 系 统 的“ 铱 星 ”发 射 中 ， 已 连 续 取 得 了 三 次 组 网 、三 次 补 网 发 射 的 成 功。中方按合同已成功发射了 ６６ 颗中的 １２ 颗铱星， 其余的铱星将由美 国德尔它火箭和俄罗斯质子火箭发射。
４．１ ＣＬＡＲＡＮＳ 算法 ＣＬＡＲＡＮＳ 是一种 ｋ－ 中心点聚类方法。它首先随机选择一个点作为
当前点， 然后随机检查它周围不超过参数 Ｍａｘｅｉｇｈｂａｒ 个的一些邻接点。 假如找到一个比它更好的邻接点， 则把它移入该邻接点， 否则把该点作 为局部最小量。然后再随机选择一个点来寻找另一个局部最小量， 直至 所 找 到 的 局 部 最 小 量 数 目 达 到 用 户 要 求 为 止 。该 算 法 要 求 聚 类 的 对 象 必 须预先调入内存， 并且需多次扫描数据集， 其时空复杂度都相当大， 虽通 过引入 Ｒ＊—树结构对其性能进行改善， 但构造和维护代价太大。该算法 对脏数据和异常数据不敏感， 但对数据输入顺序异常敏感， 且只能处理 凸形或球形边界聚类。 ４．２ ＢＩＲＣＨ 算法
卫星导航定位系统（二十四）
２００７ 年 第 １７ 卷 第 １ 期 收稿日期： ２００６－ ０９－ １５
曹来发
（ 华北电力设计院， 北京， １０００４３）
摘 要： 介绍了美国铱星（ 双星）“、 长四乙”一箭双星“、 神舟一号”试 验 飞 船“、 中 星 ２２”
通信卫星、第一颗“ 资源二号”卫星等的发射、升空和入轨情况。
２ 聚类算法基本原理概述
俗话说“： 人以群分， 物以类聚”。聚类就是利用计算机技术来实现这 一目的的一种技术。其输入是一组未分类的记录， 且事先不知道如何分 类， 也可能不知道要分成几类， 通过分析数据， 合理划分记录集合， 确定 每个记录所属的类别， 把相似性大的对象聚集为一个簇。聚类的标准是 使 簇 内 相 似 度 尽 可 能 大 、簇 间 相 似 度 尽 可 能 小 。
基 于 网 格 的 聚 类 算 法 ， 把 空 间 量 化 为 有 限 个 单 元（ 即 长 方 体 或 超 长 方体） ， 然后对量化后的空间进行聚类。此类算法具有很快的处理速度。 缺点是只能发现边界是水平或垂直的聚类， 而不能检测到斜边界。此类 算法具有很快的处理速度。时间复杂度一般由网格单元的数目决定， 而 与数据集的大小无关。此外， 聚类的精度取决于网格单元的大小。此类算 法不适用于高维情况， 因为网格单元的数目随着维数的增加而呈指数增 长。所有基于网格的聚类算法都存在下列问题： 一是如何选择合适的单 元大小和数目； 二是怎样对每个单元中对象的信息进行汇总。基于网格 的聚类算法主要有 ＳＴＩＮＧ， Ｗａｖｅ Ｃｌｕｓｔｅｒ， ＣＬＩＱＵＥ， ＭＡＦＩＡ， ＯｐｔｉＧｒｉｄ 等。 ３．５ 其他聚类
Ｗａｖｅ Ｃｌｕｓｔｅｒ 采用小波变换聚类。它首先通过在数据空间上强加一 个多维网格结构来汇总数据， 然后采用一种小波变换来变换原特征空 间， 在变换后的空间中找到密集区域。Ｗａｖｅ Ｃｌｕｓｌｅｒ 能有效处理大数据集 合， 发现任意形状的簇， 成功地处理孤立点。对于输入的顺序不敏感， 不 要求指定诸如结果簇的数目或邻域的半径等输入参数。Ｗａｖｅ Ｃｌｕｓｔｅｒ 在 效率和聚类质量上优于 ＢＩＲＣＨ， ＣＬＡＲＡＮＳ 和 ＤＢＳＣＡＮ。
摘 要： 阐述了聚类算法基本原理， 介绍了各种聚类算法， 并比较分析了几种典型聚类
算法的优点与不足， 以便于对聚类算法作进一步的研究。
关键词： 数据挖掘； 聚类算法； 数据处理
中图分类号： ＴＰ２７４
文献标识码： Ａ
１ 数据挖掘
数据挖掘是指从大型数据库或数据仓库中提取隐含的、先前未知 的 、对 决 策 有 潜 在 价 值 的 知 识 和 规 则 。 它 是 人 工 智 能 和 数 据 库 发 展 相 结 合 的 产 物 ，是 国 际 上 数 据 库 和 信 息 决 策 系 统 最 前 沿 的 研 究 方 向 之 一 。数 据 挖 掘 主 要 的 算 法 有 分 类 模 式 、关 联 规 则 、决 策 树 、序 列 模 式 、聚 类 模 式 分 析 、神 经 网 络 算 法 等 等 。聚 类 是 数 据 挖 掘 中 的 一 个 非 常 重 要 的 研 究 课 题 ， 广泛应用于各个领域， 它对未知数据的划分和分析起着非常有效的作用 并能达到合理的效果。研究和运用聚类是完成数据挖掘任务的重要手 段， 因此对聚类的研究具有重要的理论价值和现实意义。
给 定 半 径 的 领 域 中 包 含 的 对 象 不 能 少 于 某 一 给 定 的 最 小 数 目 。ＤＢＳＣＡＮ
算 法 不 进 行 任 何 的 预 处 理 而 直 接 对 整 个 数 据 集 进 行 聚 类 操 作 。当 数 据 量
５ 结语
非常大时， 就必须有大量内存支持， Ｉ／Ｏ 消耗也非常大。其时间复杂度为 Ｏ（ ｎｌｏｇｎ） ， 聚类过程的大部分时间用在区域查询操作上。ＤＢＳＣＡＮ 算法对 参数 Ｅｐｓ 及 ＭｉｎＰｔｓ 非常敏感， 且这两个参数很难确定。 ４．４ ＳＴＩＮＧ 算法
人工神经网络也常用于聚类， 如自组织特征映射（ ＳＯＭ） 网络等 。 此 外， 还有一些子空间聚类算法， 它们认为在高维数据集中， 聚类往往不是 存在于整个空间中， 而是存在于某些子空间中。它们针对高维空间数据， 寻找子空间中的聚类。主要子空间聚类算法有 ＣＬＩＱＵＥ， ＰＲＯＣＬＵＳ 等。
４ 典型聚类算法分析
ＳＴＩＮＧ 是一种格的多分辨率聚类技术。它将空间区域划分为矩形单 元， 针对不同级别的分辨率， 通常存在多个级别的矩形单元。ＳＴＩＮＧ 是独立 于查询的， 有利于并行处理和增量更新。但由于 ＳＴＩＮＧ 采用了一个多分辨 率的方法来进行聚类分析， 聚类的质量取决于网格结构的最低层粒度。并 且， ＳＴＩＮＧ 在构建一个父单元时没有考虑子单元和其相邻单元之间的关 系， 因此， 尽管该技术处理速度快， 但可能降低簇的质量和精确性。 ４．５ Ｗａｖｅ Ｃｌｕｓｔｅｒ 算法
ＤＢＳＣＡＮ 是基于密度的聚类算法。该算法利用类的密度连通性可以 快速发现任意形状的类。其基本思想是： 对于一个类中的每个对象， 在其
１４５
科技情报开发与经济
ＳＣＩ－ ＴＥＣＨ ＩＮＦＯＲＭＡＴＩＯＮ ＤＥＶＥＬＯＰＭＥＮＴ ＆ ＥＣＯＮＯＭＹ
文章编号： １００５－ ６０３３（ ２００７） ０１－ ０１４６－ ０２
科技情报开发与经济
ＳＣＩ－ ＴＥＣＨ ＩＮＦＯＲＭＡＴＩＯＮ ＤＥＶＥＬＯＰＭＥＮＴ ＆ ＥＣＯＮＯＭＹ
文章编号： １００５－ ６０３３（ ２００７） ０１－ ０１４５－ ０２
聚类算法研究综述
２００７ 年 第 １７ 卷 第 １ 期 收稿日期： ２００６－ ０６－ ２２
蔡元萃 １， 陈立潮 ２
（ １．中北大学电子与计算机科学技术学院， 山西太原， ０３００５１； ２．太原科技大学计算机科学与技术学院， 山西太原， ０３００２４）
主要的分层聚类算法有 ＢＩＲＣＨ， ＣＵＲＥ， ＲＯＣＫ， Ｃｈａｍｅｌｅｏｎ， ＡＭＯＥＢＡ， ＣＯＢＷＥＢ， Ｃｌｕｓｔｅｒｉｎｇ ｗｉｔｈ Ｒａｎｄｏｍ Ｗａｌｋｓ 算法等。
３．３ 密度聚类 很多算法中都使用距离来描述数据之间的相似性， 但是， 对于非凸
数据集， 只用距离来描述是不够的。对于这种情况， 要用密度来取代相似 性， 这就是基于密度的聚类算法。基于密度的算法从数据对象的分布密 度出发， 把密度足够大的区域连接起来， 从而可以发现任意形状的类。此 类算法除了可以发现任意形状的类， 还能够有效去除噪声。常见的基于 密度的聚类算法有 ＤＢＳＣＡＮ， ＤＢＣＬＡＳＤ， ＯＰＴＩＣＳ， ＤＥＮＣＬＵＥ 等。 ３．４ 网格聚类
３ 聚类算法分类研究
聚 类 属 于 无 监 督 学 习 。聚 类 算 法 可 以 分 为 划 分 聚 类 、层 次 聚 类 、密 度 型 聚 类 、网 格 型 聚 类 和 其 他 聚 类 等 几 种 。 ３．１ 划分聚类
划分聚类算法把数据点集分为 ｋ 个划分， 每个划分作为一个聚类。 它一般从一个初始划分开始， 然后通过重复的控制策略， 使某个准则函 数最优化， 而每个聚类由其质心来代表（ ｋ－ ｍｅａｎｓ 算法） ， 或者由该聚类中 最靠近中心的一个对象来代表（ ｋ－ ｍｅｄｏｉｄｓ 算法） 。划分聚类算法收敛速 度快， 缺点在于它倾向于识别凸形分布大小相近、密度相近的聚类， 不能 发现分布形状比较复杂的聚类， 它要求类别数目 ｋ 可以合理地估计， 并 且 初 始 中 心 的 选 择 和 噪 声 会 对 聚 类 结 果 产 生 很 大 影 响 。主 要 的 划 分 聚 类 算 法 有 ｋ － ｍｅａｎｓ， ＥＭ， ｋ － ｍｅｄｏｉｄｓ， ＣＬＡＲＡ， ＣＬＡＲＡＮＳ 等 。 常 见 的 ｋ － ｍｅｄｏｉｄｓ 算法有 ＰＡＭ 算法、ＣＬＡＲＡ 算法、ＣＬＡＲＡＮＳ 算法。 ３．２ 分层聚类
分 层 聚 类 算 法 把 数 据 对 象 分 组 而 形 成 一 个 聚 类 树 。分 层 聚 类 算 法 分 为两大类：聚结型和分裂型。聚结型算法采用自底向上的策略， 首先把每 个对象单独作为一个聚类， 然后根据一定的规则合并成为越来越大的聚 类， 直到最后所有的对象都归入到一个聚类中。大多数分层聚类算法都 属于聚结型算法， 它们之间的区别在于类间相似度的定义不同。与聚结 型算法相反， 分裂型算法采用自顶向下的方法。一般情况下不使用分裂 型方法， 因为在较高的层很难进行正确的拆分。纯粹的分层聚类算法的 缺点在于一旦进行合并或分裂之后， 就无法再进行调整。现在的一些研 究侧重于分层聚类算法与循环的重新分配方法的结合。