-
数据挖掘层次聚类算法研究综述
摘
要
聚类问题是数据挖掘中的重要问题之一，是一种非监督的学习
方法。分层聚类技
术在图像处理、
入侵检测和生物信息学等方面
有着极为重要的应用，
是数据挖掘领域的研究
热点之一。
本文总结了分层聚类算法技术的研究现状，
分析算法性能的主要差异，
并指出其
今后的发展趋势。
关键词
层次聚类，数据挖掘，聚类算法
Review of hierarchical clustering
algorithm in Data Mining
Abstract
Clustering
problem
of
data
mining
is
one
of
important
issues,
it
is
a
kind
of
unsupervised
learning
methods.
Stratified
cluster
technology
in
image
processing,
intrusion
detection
and
bioinformatics
has
extremely
important
application
and
is
data
mining
area
of
research
one of the hotspots. This paper summarizes the
layered clustering algorithm technology
research,
analyzes
the
main
difference
arithmetic
performance,
and
pointed
out
the
future
development trend.
Keywords
Hierarchical
clustering
，
Data
mining
，
Clustering algorithm
1
引言
随着
计算机技术的发展，信息数据越来越多，如何从海量数据中提取对人们有价值的
信息已经
成为一个非常迫切的问题。由此产生了数据挖掘技术，它是一门新兴的交叉学科，
汇集了
来自机器学习、模式识别、数据库、统计学、人工智能等各领域的研究成果。聚类分
析是
数据挖掘中的一个重要研究领域。
它在图像处理、
入侵检测和生
物信息学等方面有着极
为重要的应用。
数据挖掘是从大量数据中
提取出可信、
新颖、
有效并能被人理解的模式的
高级处理过程。
其目标是从数据库中发现隐含的、
有
意义的知识。
聚类分析作为一个独立
的工具来获得数据分布的情
况，是数据挖掘的一个重要研究分支。
在数据挖掘领域，研究工作己经集中在为大型数据库的有效和实际的聚类分析寻找适
当的方法。
活跃的主题集中在聚类方法的可伸缩性，
方法对聚类
复杂形状和类型的数据的有
效性，
高维聚类分析技术，
以及针对大型数据库中混合数值和分类数据的聚类方法。
迄今为
止，
人们己经提出了很多聚类算法，
它们可以分为如下几类：划分方法、
层次方法、
基
于密度的方法、
< br>基于网格的方法和基于模型的方法，这些算法对于不同的研究对象各有优
缺点。在
聚类算法当中，
划分方法和层次方法是最常见的两类聚类技术
，其中划分方法具
有较高的执行效率，
而层次方法在算法上比较
符合数据的特性，
所以相对于划分方法聚类的
效果比较好。
[1]
层次聚类算法和基于划分的
K-M
eans
聚类算法是实际应用中聚类分析的支柱，算法简
单、<
/p>
快速而且能有效地处理大数据集。
层次聚类方法是通过将数据组织
为若干组并形成一个
相应的树来进行聚类的。
根据层是自底而上
还是自顶而下形成。
一个完全层次聚类的质量由
于无法对己经做
的合并或分解进行调整而受到影响。但是层次聚类算法没有使用准则函数，
它所潜含的对
数据结构的假设更少，所以它的通用性更强。
2
基于层次的聚类算法
2.1
凝聚的和分裂的层次聚类
层次聚类是
聚类问题研究中一个重要的组成部分。
分层聚类的基本原则可以表述为：
如
果输入
n
个数据点
(
或数集
)
，我们定义
n
个数簇，其中每个簇含一个数据。确定距离（簇与
簇之间的距离可以通过很多的方法来定义，
最常用的是单连接度量。
其定义两个簇之间的距
离为一个簇中所有成员与另一簇中所有成员之间
的最短距离。
）
层次化聚类算法可以进一步地分为两类：凝聚和分裂。
凝聚算法：在每层选择两个最相似的簇被合并，合并后的簇在更高层参与类似的合并。
分裂算法：
它首先把整个数据集看成一个簇，
然后依据数据集的特性在每一层分成越来
越小的簇。非层次化方
法的聚类算法也有很多，其中，
K-Means
算法是最经典的
，还有
K-Means
的变种。
层次化聚类算法就是将数据对象组成一棵聚类的树。
根据层次分解是
自底向上生成还是
顶向下生成，层次的聚类方法可以细分为凝聚的和分裂的层次聚类。<
/p>
凝聚的层次聚类：
凝聚的层次聚类是自
底向上的策略。
首先将每个对象作为一个类，
然
后合并这些原子类为越来越大的类，
直到所有的对象都在一个类中，
或者某个终结条件被满
足。
分裂的层次聚类是种自
顶向下的策略与凝聚的层次聚类相反，
它首先将所有对象置于一
个类中，
然后逐渐细分为越来越小的类，
直到每个对象自成一类
，
或者达到了某个终结条件，
例如达到了某个希望的类数目，<
/p>
或者两个最近的类之间的距离超过了某个闽值。
绝大多数聚
类方法属于这一类，它们只是在簇间相似度的定义有所不同。
分裂的层次聚类：
这种自顶向下的策略与凝聚的层次聚类相反，
它首先将所有对象置于
一个簇中，
然后逐渐细
分为越来越小的簇，
直到每个对象自成一簇，
或者达到了某个终
止条
件，
例如达到了某个希望的簇数目，
或者两个最近的簇之间的距离超过了某个阀值。
层次化
聚类方
法尽管简单，
但如何恰当地选择合并或分裂点，
是个很困难的工
作，
这样的选择是非
常关键的，
因为一
旦一组对象被合并或者分裂，
下一步的处理将在新生成的簇上进行。
已做
的处理不能被撤消，
聚类之间也不能交换对象。
如果在某一步没有很好的选择合并或者分裂
的决定，可能会导致低质量
的聚类结果。
而且，这种聚类方法不具有很好的可伸缩性，
因为
合并或者分裂的决定需要检查和估算大量的对象或簇。
[2]
2.2
改进的层次聚类算法基本思想
按照原层次聚类算法，当依照最小距离
d
（
i
，
j
）
合并了第
i
和第
j
簇后，必须重新计算
新合并的簇
d
（
i
，
j
）和
原有簇的距离，按照最小距离的计算方法，
d[(k)
，
(r
，
s)]=min d[(k)
，
(r)]
，
d[(k
)
，
(s)]
，其中
< br>d[(k)
，
(r)]
与
d[(k)
，
(s)]
来源于初始化的距离矩阵，
也就是说
d[(k)
，
(r
，
s)]
的值必然也就是初始化距离矩阵中的某个值，同理，当合并了一个簇后，新的距离矩阵
里的所有值也就都是来源于初始化的距离矩阵，
当然新的距离矩阵内的最小值
也来源于初始
化的距离矩阵。
层次聚
类算法是按照最短距离法来进行层次聚类的，当第一次合并了其中最小的一个
d(i
，
j)
后，
产生了
新的距离矩阵，
由于新的距离矩阵中的所有值均来源于初始化的距离矩阵，
再从新的距离矩阵中取最小值，
那么这个最小值必定是除了第一次合并后的最
小值外，
初始
化距离矩阵中的次小值。
也就是说，
假定我们合并掉了初始化距离矩阵中的最小值后，
下
一
个要合并的必定就是初始化距离矩阵中的次小值，
依次递推下
去，
直到所有的簇都被合并完
为止。
2.3
改进的层次聚类算法
改进层次算法的聚类质量的一个主要方向是将层次聚类和其他的聚类技术进行集成，
形
成多阶段聚类，
许多学者在基于多阶段聚类方法
的思想之上提出了几种经典的层次聚类方法
的改进算法。这里主要讲
BIRCH
算法，它首先用树结构对对象进行层次划分，然后采用其
他的聚类算法对聚类结果进行求精。
[4]
BIRCH(Balanced Iterative Reducing and
Clustering using Hierarchies)
算法是一个集成的层<
/p>
次聚类方法。它包含两个重要概念：聚类特征
(CF)
和聚类特征树
(CF
tree)
，它们用于概括聚
-
-
-
-
-
-
-
-
-
上一篇：流体动力学专业词汇讲解
下一篇：流行病学 描述性研究