第
28
卷第
1
期
2008
年
1
月
北京理工大学学报
Vo
l.
28
No.l
]an. 2008 Transactions
of
Beijing
Institute
of
Technology
基于凝聚的层次聚类算法的改进
石剑飞
1
，
2
闰怀志
2
牛占云
1
(1.北京理工大学计算机网络攻防对抗技术实验室，北京
100081;
2.
北京理工大学软件学院，北京
10008
1)
摘
要:为提高基于凝聚的层次聚类算法的准确率.在研究了空间级约束适用情况的基础上，以
Single
Link
算法
为例，验证了空间级约束条件对聚类结果的影响与实例级约束
Single
Link
算法相比，空间级约束
Single
Link
算法
只需较少约束条件即可达到较高准确率.实验结果证明，空间级约束可以有效提高聚类的准确率
关键词:聚类算法:实例级约束;空间级约束
中图分类号:
TP
393
文献标识码
:A
文章编号:
1001-0645 (2008 )01-0066-04
Improved
Algorithm Based
on
Agglomerative
of
Hierarchical
Clustering
SHI
Jian-fei
1
,2,
YAN
Huai-zhi
2
,
NIU
Zhan-yun
1
(1.
Lab
of
Network Defense Technology,
Beijing
Institute
of
Technology,
Beijing
100081, China;
2.
School
of
So
ftware,
Beijing
Institute
of
Technology,
Beijing
100081 , China)
、
Abstract:
To
enhance
the
accuracy
of
hierarchical
clustering
algorithm
,
based
on
a
study
of
space-
constrained
application
,
and
using
the
Single
Link
algorithm
as
an
example
,
the
impact
of
space-
constrainment
is
certificated
to
the
result.
Co
mpared
with
th
巳
case-constrain
Single
Link
algorithm
,
space-constrained
Single
Link
algorithm
needs
less
constrained
conditions
to
achieve
higher
accuracy.
Experiments
showed
the
space-constrainment
can
enhance
the
clustering
accuracy
effectively.
Key
words:
clustering;
case-constrained;
space-constrained
聚类就是将数据对象分组变成多个簇，使同一
个簇中的对象具有较高的相似性，而不同簇中的对
象具有较大的相异性.良好的聚类方法产生的聚类
结果具有簇内对象高度相似，簇间对象很少相似的
恃性[1)
聚类过程的实质是寻找聚类目标函数最优解的
优化过程.基于层次的聚类方法
[2)
将数据对象在不
同阶段组成不同粒度的簇，并在簇的分裂和合并过
程中不断改善聚类的效果，以达到逐步求精的目的.
层次聚类法根据层次分解方向可以分为凝聚
[3)
的
和分裂的层次聚类.
作者讨论了一种改进约束条件的凝聚层次聚类
算法，通过使用空间级约束条件改进实例级约束的
层次聚类算法的性能，以
Single
Link
算法为例，实
收稿日期:
2007
-
07
-
05
基金项目:国家部委基础科研项目
(20021823)
现空间级约束的算法并验证改进后算法的性能.
1
实例级约束的局限性分析
虽然针对算法添加实例级约束的方法使聚类结
果满足了所有约束条件，却没有深入挖掘这些约束
中的隐含信息
[4)
例如，图l(
a)
为原始数据集，实例
有两个属性，可以用平面图直观表示.每个叉号代
表一个数据.图
l(b)
的两双线表示被连接的两个实
例属于必相邻数据集.图l(
b)
与图
l(c)
的聚类结
果都满足所有的约束，但可以看出，图l(
c)
的聚类
结果较好.这是因为实例级别的约束隐性地改变了
这两个聚类周围的实例间的关系，也就是使一个空
间的距离产生了变化.不仅要使属于必相邻约束集
中的实例对分配到同一个聚类中，还要使距这两个
作者简介:石剑飞(1
982-)
，男，博士生，
E-mail:jfshi0311@163.com;
I
可怀志(1
975
一).男，副教授
资源评论
