文档介绍：第卷第期电子与信息学报
年月
用于数据挖掘的聚类算法
姜园”’张朝阳’仇佩亮周东方,
浙江大学信息与通信工程研究所杭州
”解放军信息工程大学郑州
摘要数据挖掘用于从超大规模数据库中提取感兴趣的信息。聚类是数据挖掘的重要工具,根据数据间的相似性
将数据库分成多个类,每类中数据应尽可能相似。从机器学习的观点来看,类相当于隐藏模式,寻找类是无监督学
习过程。目前己有应用于统计、模式识别、机器学习等不同领域的几十种聚类算法。该文对数据挖掘中的聚类算法
进行了归纳和分类,总结了类算法并分析了其性能特点。
关键词数据挖掘,聚类,分层聚类,分割聚类,
中图分类号文献标识码文章编号

’
”

引言各类算法分析
数据挖掘用于从超大规模数据库中提取感兴趣分层聚类算法
的信息。聚类是数据挖掘的重要工具。聚类通过建立数学模分层聚类算法通过建立系统树图进行分类,每个树节点
型,根据数据相似性将数据库划分为不同的部分,使得类内都有其子类,聚类可在不同层次进行。分层聚类又分为两种
数据尽可能相似,类间数据差异尽可能大。不同于一般的聚类型凝聚算法自底向上和分裂算法自顶向下。凝
类算法,用于数据挖掘的聚类算法处理超大规模数据库,且聚算法首先将每个样本看成一个类,然后根据相应条件将其
数据属性的种类非常多,因此要尽量降低算法的计算复杂与最邻近样本融合为另一个类,如此迭代进行。分裂算法首
度。先将所有的样本看成一个类,然后进行迭代分裂。分层聚类
聚类算法通常有分层聚类、分割聚类、基于密度的聚类、需要预先设定一个终止条件如设定类数目,当凝聚或者
基于栅格的聚类、字符属性联合聚类、高维数据聚类和神经分裂过程满足该条件时终止算法。该类算法的优点是灵活
网络聚类等种。这种分类并非完备正交的,相互之间有交性,可以在不同层次进行分类可以处理任何类型的相似性
叉。评价聚类算法的优劣主要考虑其所能处理数据属性的种可以处理任何属性的数据。该类算法的缺点是算法终止条
类,对的可扩展性,处理高维数据和不规则数据的性
件不明确在处理过程中没有向上层反馈信息,没有优化过
能,抗干扰性和算法的时间复杂度。本文对数据挖掘中现有
程。典型的分层聚类算法以连接矩阵为处理对象,矩
聚类算法进行了归纳和分类,总结了各种算法思想并分析其
阵元素是样本间距离。用于时,这个矩阵太大以至于
性能特点。
无法运算。通常采用两种方法将该矩阵稀疏化设立门限,
收到,改回
国家自然科学基金资助课题
电子与信息学报第卷
将小于门限值的元素置零矩阵中只保留各样本与若干最邻也是可变的,目前己经有商业应用的软件包。综合考虑聚类
近样本间距离。形成趋势、聚类分析和聚类有效性问题聚类数目的合理
连接矩阵不能解决具有不规则形状的数据库聚类问题。性,将和提出的平方空间抽样原理进行扩
算法和展,可以把聚类形成趋势和聚类有效性两个问题归纳为模式
算法较好地解决了这个问题。算法用子集在特征空间的单峰检验问题,能有效降低算法复杂度
几个具有代表性的分散点表示各类,通过选取适当的点代表底,便于实现超大规模数据库的聚类。单变量时间序列的
任意形状的类,在迭代过程