整体相似度＝ 各对象点与中心点距离总和 簇内对象总数
１．３ 相异度矩阵
存储 ｎ 个对象两两之间的近似性， 其表现形式是一个 ｎ×ｎ 维的矩阵， 如图 ２ 所示。
$%０
’ (
%
(
%ｄ（ ２， １） ０
(
%
(
%%ｄ（ ３， １） ｄ（ ３， ２） ０
( (
%
(
% %
…
……
( (
%%&ｄ（ ｎ， １）
ｄ（ ｎ， ２）
若｜ｏｉ－ Ｃｌ｜＜｜ｏｉ－ Ｃｒ｜， 则 ｏｉ∈左子树， 否则 ｏｉ∈右子树， 其中 ｏｉ 取遍 当前簇中所有对象；
（ ４） 当 聚 类 数 目 ｍ≥４ 时 ， 计 算 各 簇 间 的 相 异 度 及 熵 值 和 ｅｂ， ｅｂ＝
ｍ
!ｅｉ； ｉ＝１ （ ５） 合 并 最 相 似 的 两 个 簇 ， 得 ｍ－ １ 个 簇 ， 计 算 合 并 后 各 簇 的 熵 值 ｍ－ １
Ｋｅｙｗｏｒ ｄｓ： ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ， ｄｉｓｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅ， ｅｎｔｒｏｐｙ， ｏｖｅｒａｌｌ ｓｉｍｉｌａｒｉｔｙ， ｃｌｕｓｔｅｒ ｑｕａｌｉｔｙ
数 据 挖 掘 是 从 大 量 数 据 中 提 取 出 可 信 、新 颖 、有 效 并 能 被 人 理 解 的 模 式 的 高 级 处 理 过 程 。其 目 标 是 从 数 据 库 中 发 现 隐 含 的 、有 意 义 的 知 识 。 聚 类 分 析 作 为 一 个 独 立 的 工 具 来 获 得 数 据 分布的情况， 是数据挖掘的一个重要研究分支。所谓聚类， 就是 将物理或抽象对象的集合分组成为由类似的对象组成的多个 类的过程。由聚类所生成的簇是一组数据对象的集合， 在同一 个类中的对象之间具有较高的相似度， 而不同类中的对象差别 较大。
Ｓｈａｎｎｏｎ 提 出 信 息 熵 概 念 的 目 的 是 用 来 解 决 随 机 事 件 或 对信号所含信息量大小进行评价。设 Ｘ 是取有限个值的随机
ｎ
! 变 量 ， ｐｉ＝ｐ｛Ｘ＝ｘｉ｝， ｉ＝１， ２， … ， ｎ， 则 Ｘ 的 熵 定 义 为 Ｈ （ ｘ） ＝－ ｐｉ ｉ＝１
ｌｏｇ ｐｉ。信息熵是由事物内部属性客观决定的， 熵的值是各个概 率值的函数。信息论中还证明当各个概率的值都相同时， 信息熵 的值最大。这个特性可以用来判断一个簇中同类元素出现的概 率。当不同类元素均匀分布且出现概率相等时， 其熵值最大； 如 果某一类元素出现机率较高， 则其熵值较小； 当集合中只有某一 类元素出现时， 其熵值为 ０。假设集合由 Ａ 和 Ｂ 两类对象组成， 则该集合的熵值随 Ａ 类对象所占比例的变化曲线如图 １ 所示。
２．２ 算法流程
输入： 包含 ｎ 个对象的数据库和聚类停止参数（ 熵阈值） 。 输出： 聚类结果。 方法： （ １） 将所有对象置于一个簇中； （ ２） ｒｅｐｅａｔ （ ３） 计算当前所有簇的如下值：
ａ．每个簇的平均值（ 重心） ｗ； ｂ．在簇中随机选取一对象 Ｃｌ（ 不与簇重心重合） ； ｃ．根据公式 Ｃｒ＝ｗ－ （ Ｃｌ－ ｗ） 计算 Ｃｒ； ｄ．将 当 前 簇 一 分 为 二 ：
迄今为止， 人们己经提出了很多聚类算法， 它们可以分为 如 下 几 类 ： 划 分 方 法 （ ｐａｒｔｉｔｉｏｎｉｎｇ ｍｅｔｈｏｄ） 、层 次 方 法 （ ｈｉｅｒａｒ－ ｃｈｉｃａｌ ｍｅｔｈｏｄ） 、基 于 密 度 的 方 法（ ｄｅｎｓｉｔｙ－ ｂａｓｅｄ ｍｅｔｈｏｄ） 、基 于 网 格 的 方 法 （ ｇｒｉｄ－ ｂａｓｅｄ ｍｅｔｈｏｄ） 和 基 于 模 型 的 方 法 （ ｍｏｄｅｌ－ ｂａｓｅｄ ｍｅｔｈｏｄ） ， 这些算法对于不同的研究对象各有优缺点。
…
…
０
(( )
图 ２ 相异度矩阵
图 ２ 中 ｄ（ ｉ， ｊ） ＝ｄ（ ｊ， ｉ） ， 而 且 ｄ（ ｉ， ｉ） ＝０。 如 何 计 算 相 异 度 是
非常重要的， 因为这影响到聚类的结果。对于具有不同数据类 型的对象以及混合类型的对象， 其相异度的计算方法各不相 同。
对象间相异度的计算可以扩充到簇间的相异度评价， 各簇 的中心点确定之后， 就可以按照上述方法来计算簇间相异度。
的策略， 首先将每个对象作为一个簇， 然后合并这些原子簇为 越来越大的簇， 直到所有的对象都在一个簇中， 或者满足某个 终止条件。分裂的层次聚类采用自顶向下的策略， 首先将所有 对象置于一个簇中， 然后逐渐细分为越来越小的簇， 直到每个 对象自成一簇， 或者满足某个终止条件。
这里我们将层次聚类和其他的聚类技术（ 划分方法） 进行 集成， 并进行动态的分裂与合并来提高层次方法的聚类质量。
基于层次与划分方法的聚类算法研究
甄彤 （ 华中科技大学控制科学与工程系， 武汉 ４３００７４） （ 河南工业大学信息科学与工程学院， 郑州 ４５００５２）
Ｅ－ ｍａｉｌ： ｚｔ＠ｈａｕｔ．ｅｄｕ．ｃｎ
摘 要 针对在层次聚类算法中， 一个分裂或合并被执行， 就不能修正， 其聚类质量受到限制的缺陷， 提出了利用簇间相 异度及基于信息熵或整体相似度的聚类质量评价标准， 在簇分裂过程中动态的进行簇的合并与分裂的算法。仿真实验结 果证明， 该算法具有使结果簇更紧凑和独立的效果， 具有更好的聚类质量。 关键词 层次聚类 相异度 信息熵 整体相似度 聚类质量 文章编号 １００２－ ８３３１－ （ ２００６） ０８－ ０１７８－ ０３ 文献标识码 Ａ 中图分类号 ＴＰ３０１．６
在聚类算法当中， 划分方法和层次方法是最常见的两类聚 类技术， 其中划分方法具有较高的执行效率， 而层次方法在算 法上比较符合数据的特性， 所以相对于划分方法聚类的效果比 较好。但是层次聚类算法中， 一旦一个分裂或合并被执行， 就不 能修正， 其聚类质量受到限制， 而且该算法执行速度相对地较 慢。本文结合两者特性， 在分裂的层次聚类基础上， 在簇的分裂 过程中， 采用 ｋ－ ｍｅａｎｓ 算法中以簇中对象的重心来表示一个簇 的方法， 并且在合并最相似的两个簇之后， 利用聚类质量评价
２ 改进算法 ２．１ 改进算法概述
层次的聚类方法的缺陷在于， 一旦一个步骤（ 合并或分裂） 完成， 它就不能被撤销。为了改进层次聚类的结果， 我们在分裂 的层次聚类中动态的进行簇的分裂与合并， 也即是在分裂完成 之后， 按照一定的准则合并簇， 同时评价合并前后的聚类质量， 如果合并使得聚类质量下降， 就取消合并， 从而提高聚类效果。
合并准则： 计算当前各簇间的相异度， 生成相异度矩阵， 合 并具有最小相异度的两个簇。
取消合并准则： 假设使用 Ｅｎｔｒｏｐｙ 来评价聚类质量， 计算合 并前后各簇的熵值和， 如果合并之后熵值增大， 则取消合并； 反 之， 保留合并。若使用整体相似性来评价聚类质量， 可以采用类 似方法进行， 总是使聚类质量向好的方向发展。
ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｗｕｈａｎ ４３００７４） （ Ｃｏｌｌｅｇｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｈｅｎａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｚｈｅｎｇｚｈｏｕ ４５００５２）
Ａｂｓｔｒ ａｃｔ： Ｈｉｅｒａｒｃｈｉｃａｌ ｍｅｔｈｏｄｓ ｓｕｆｆｅｒ ｆｒｏｍ ｔｈｅ ｆａｃｔ ｔｈａｔ ｏｎｃｅ ａ ｍｅｒｇｅ ｏｒ ｓｐｌｉｔ ｉｓ ｄｏｎｅ， ｉｔ ｃａｎ ｎｅｖｅｒ ｂｅ ｕｎｄｏｎｅ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｈｉｅｒａｒｃｈｉｃａｌ ａｎｄ ｐａｒｔｉｔｉｏｎｉｎｇ ｍｅｔｈｏｄ．Ｄｕｒｉｎｇ ｔｈｅ ｓｐｌｉｔ ｐｒｏｃｅｓｓ， ｃｌｕｓｔｅｒｓ ａｒｅ ｍｅｒｇｅｄ ａｎｄ ｓｐｌｉｔ ｄｙｎａｍｉｃａｌｌｙ ｂｙ ｕｓｉｎｇ ｄｉｓｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅ ｂｅｔｗｅｅｎ ｃｌｕｓｔｅｒｓ ａｎｄ ｅｎｔｒｏｐｙ ｏｒ ｏｖｅｒａｌｌ ｓｉｍｉｌａｒｉｔｙ ｔｏ ｅｖａｌｕａｔｅ ｔｈｅ ｃｌｕｓｔｅｒ ｑｕａｌｉｔｙ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔ ｓｈｏｗｓ ｔｈｅ ｂｅｔｔｅｒ ｒｅｓｕｌｔｓ ｗｉｔｈ ｍｏｒｅ ｃｏｍｐａｃｔｎｅｓｓ ａｎｄ ｓｅｐａｒａｔｉｏｎ．
ቤተ መጻሕፍቲ ባይዱ
Ｒｅｓｅａｒ ｃｈ ｏｆ Ｃｌｕｓｔｅｒ ｉｎｇ Ａｌｇｏｒ ｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｈｉｅｒ ａｒ ｃｈｉｃａｌ ａｎｄ Ｐａｒ ｔｉｔｉｏｎｉｎｇ Ｍｅｔｈｏｄ
Ｚｈｅｎ Ｔｏｎｇ （ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｎｔｒｏｌ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ
标准来决定是否取消合并以提高聚类质量。
１ 相关概念与原理 １．１ 划分与分层算法基本原理
给定一个包含 ｎ 个数据对象的数据库， 以及要生成的簇的 数目 ｋ， 一个划分算法采用一个划分准则将数据对象划分为 ｋ 个部分（ ｋ≤ｎ） ， 其中每个部分代表一个簇。最著名与最常用的 划分方法是 ｋ－ ｍｅａｎｓ 和 ｋ－ ｍｅｄｏｉｄ。
一 个 层 次 的 聚 类 方 法 将 数 据 对 象 组 成 一 颗 聚 类 的 树 。根 据 层次分解是自底向上还是自顶向下形成， 层次的聚类方法可以 分 为 凝 聚 的 和 分 裂 的 层 次 聚 类 。凝 聚 的 层 次 聚 类 采 用 自 底 向 上
基金项目： 河南省自然科学基金资助项目（ 编号： ２００４６０１０３６） 作者简介： 甄彤（ １９６４－ ） ， 男， 博士生， 副教授， 主要研究方向： 系统工程。 １７８ ２００６．０８ 计算机工程与应用
１．２ 聚类质量评价标准
对聚类质量进行评价的常用技术有 Ｅｎｔｒｏｐｙ 和整体相似度。 如果在分类之前已知聚类结果， 只是将聚类结果与已知聚类结 果进行比较， 常使用 Ｅｎｔｒｏｐｙ 的概念； 如果在聚类操作之前对聚 类结果一无所知， 我们常用整体相似度作为对聚类质量的评价。 １．２．１ Ｅｎｔｒｏｐｙ