[收稿日期] 2009 03 19
[作者简介] 张丽芳
(
1981
)
, 女 , 2003 年大学毕业 , 硕士 , 助教 , 现主要从事数据分析方面的研究工作。
3 种聚类算法性能比较分析
张丽芳
(
长江大学信息与数学学院数学系 , 湖北 荆州 434023
)
[摘要] 对 3 种著名的聚类算法进行了对比分析 , 在多类高维 UCI 数据集上进行了试验 , 最后对试验结果
进行了分析。
[关键词] 聚类 ; K2MEANS 算法 ; COBWEB 算法 ; DENCLU E 算法
[中图分类号] TP311 [文献标识码] A [文章编号] 1673 1409
(
2009
)
02 N250 02
1 3 种算法简介
聚类算法众多 , 其中著名的算法有 K2MEANS 算法、COBWEB 算法和 DENCLU E 算法。
K2MEANS 算法最早由 MacQueen 提出来的。在这个算法中 , 每个类用该类中现有对象的平均值表
示。K2M EANS 算法非常简单 , 在解决一些实际问题时 , 也很容易完成。该算法在处理致密型和超球体
型的聚类中效果很好。由于其时间复杂度是 O
(
Nkt
) (
其中 , N 为样本数; k 为聚类数; t 为迭代次数
)
, 因
此对处理大型数据集也是相对可伸缩和高效率的
[1 ]
。
COBWEB 算法是一个通用且简单的增量式的概念聚类算法。COBWEB 算法用分类树的形式来表现
层次聚类。为了利用分类树来对一个对象进行分类 , 需要利用一个匹配函数来寻找“最佳的路径”,
COBWEB 算法用了一种启发式的评估衡量标准 , 将分类效用 CU
(
category utility
)
来指导树的建立过
程。该算法能够自动调整类的数目的大小 , 而不像其他算法那样自己设定类的个数 , 但 COBWEB 算法
中的 2 种操作对于记录的顺序很敏感 , 为了降低这种敏感性 , 该算法引入 2 个附加操作 : 合并和分解。
可以根据 CU 值来确定合并和分解操作 , 从而达到双向搜索的目的。COBWEB 算法的缺点是 : ①它假
设每个属性上的概率分布是彼此独立的 , 由于属性间经常是相关的 , 这个假设并不总是成立。这给该方
法带来一定的局限性。②聚类的概率分布表示更新和存储聚类相当繁复 , 因为时间和空间复杂度不只依
赖于属性的数目 , 还取决于每个属性的值的数目 , 所以当属性有大量的取值时情况变得很复杂。③分类
树对于偏斜的输入数据不是高度平衡的 , 它可能导致时间和空间复杂性的剧烈变化
[2 ]
。
DENCLUE
(
Density2based Clustering
)
算法是一个基于一组密度分布函数的聚类算法。DENCLUE 算
法的优点是 : ①它有一个坚实的数学基础 , 概括了其他的聚类方法 , 包括基于分割的、层次的以及基于
位置的方法。②对于有大量“噪声”的数据集合 , 它有良好的聚类特性。③对高维数据集合的任意形状
的聚类 , 它给出了简洁的数学描述。④它使用了网格单元 , 只保存实际包含数据点的网格单元的信息。
它以一个基于树的存取结构来管理这些单元 , 因此比其他算法
(
如 DBSCAN 算法等
)
的速度要快。
DENCLU E 算法的缺点是 : 要求对密度参数
σ
和噪声阈值
ξ
进行仔细的选择 , 因为这样的参数选择可能
明显地影响聚类结果的质量 , 即对参数比较敏感
[3 ]
。
2 3 种算法试验
211 试验数据
表 1 数据集 Glass 的描述表
数据集 样本总数 类别数 属性数
Glass 214 6 9
本试验所使用的数据集 Glass 从 UCI 数据库
(
国际通用机器学习训练数据库
)
中获得 , 该数据集
的详细描述见表 1。从表 1 中可看出 , 该数据集是多
类高维数据。
·052·
长江大学学报
(
自然科学版
)
2009 年 6 月 第 6 卷 第 2 期 : 理工
Journal of Yangtze University ( Nat Sci Edit) Jun12009 , Vol16 No12 : Sci & Eng
评论1