第21卷第1期
重庆科技学院学报（自然科学版)2019年2月
WEKA
平台下的聚类分析算法比较研究
韩存""，2
叶球孙1
(1.
武夷学院数学与计算机学院，福建武夷山354300
;
2.
认知计算与智能信息处理福建省高校重点实验室，武夷山354300
)
摘要:介绍
K -
means、
DBSCAN、
EM、
FarthestFGt等4种常用的聚类算法，
并在
WEKA中使用这些算法对
RG数据
集进行了聚类实验。
实验结果表明，
与
DBSCAN、
EM、
FarthestFlrst等聚类算法相比，
K -
means算法在误判率、
运行时
间、
生成簇数、
迭代次数方面与人工判断的吻合度最高。
关键词:聚类分析；
聚类算法；
实验；
WEKA %
I
d
中图分类号:
TP301.6
文献标识码:
A
聚类分析是数据挖掘研究中一个非常活跃的研
究领域。
数据挖掘的一个重要任务是发现众多数据
中的积聚现象，
然后对其进行定量化描述。
聚类分
析是在对数据不作任何假设的条件下，
用数学方法
研究和处理所给对象的分类以及各类之间的亲疏程
度，
其目标是要将具有相似特征的样本数据归为一
类，
并使得类内差异小、
类间差异大。
聚类与分类不
同。
在分类模型中存在样本数据，
这些数据的类标
号是已知的，
分类的目的是从训练样本集中提取出
分类的规则，
用于对其他类标号未知的对象进行类
表示。
聚类是在不知道目标数据的有关类的信息的
情况下，
以某种度量为标准将所有的数据对象划分
到各个簇中。
聚类分析因此又被称为无监督的学
习[1]。
聚类算法的目的是要寻找数据中潜在的自然
分组结构和特定的关系。
目前已经存在许多聚类算
法。
本次研究，
将通过实验对几种常用的聚类算法
进行比较分析。
1
常用的几种聚类算法概述
不同的聚类算法在进行决策树分析时存在一定
的差异。
评价聚类算法性能的指标主要有3
个:一
是正确预测的能力，
即预测的准确率;
二是可解释
性，
产生的有关模型要易于理解;
三是速度，
即产生
规则的时间越短越好[2]。
另外，
与人工判断的吻合
度是最直观的评判准则之一。
在众多的聚类算法文章编号
：1673 -1980(2019)01 -0090
-04
中，基于划分的K- means
算法、基于模型的EM
算
法、基于密度的DBSCAN
算法和基于分层的Far-
thetFGt
算法是比较常用的算法，我们主要比较分
析这4
种聚类算法的性能。
1.1 K - means
算法
1.1.1 K - means
的原理及流程
1967
年由 1 B. Macqueen
提出的 K- means
算
法，目前已经成为数理统计、模式识别、机器学习和
数据挖掘等领域应用最普遍的一种聚类算法，并有
多种变形算法，组成了 K - means
算法家族。
按照K - means
算法，先是进行粗略的分类，然
后根据某种最优的原则修改不合理的分类，直到类
分比较合理，形成最终的分类结果。因此，首先需要
随机地选择A
个对象，每个对象初始代表一个簇的
平均值或中心。接着将剩余的每个对象，根据其与
各个簇均值的距离，分派给最近的簇;
然后计算每个
簇的新均值。这个过程不断重复，直到准则函数收
敛。通常采用平方误差准则，其定义如下[3]:
%
E%\
p-
ml\2
f=1
p/Ci
其中:P
是空间中的点，表示给定的数据对象;T
是
簇[
的平均值。
K - means
均值划分算法的流程如下。
Input:K(
簇的数目），4(
包含ra
个对象的数
集)
收稿日期
:2018
-11
-20
基金项目
：福建省科技厅自然科学基金项目“
VCN智模变进制乘法计算杂性研究$(201711406)
作者简介
:韩存鸽（1979 —），女，硕士，讲师，研究方向为数据库、数据挖掘。
•
90 •韩存鸽，等:WEKA平台下的聚类分析算法比较研究
Output -X个簇的集合
方法
:（
1)从
D中任意选择
A个对象作为初始
簇中心；（
2) repeat;( 3 )根据簇中对象的均值，将每
个对象指派到最相似的簇；（
4)更新簇均值，即计算
每个簇中对象的均值；（
5)簇均值不再发生变化，则
结束）
1.1.2 K - means应用举例
坐标上有
5个点丨
i■，进行聚类
分析。
5个二维样本为
-?=(0,0)，？
= (5,2)，
? = (1. 5,0),? = (0,2),? = (5,0)〇
假设
O = 2〇
Step 1 -随机分为
2个簇，计算质心
M。
C1 =(?,?,?) C2 = (?,?)
M1 = {0+5+1.5/3,0+2+0/33 =|2.17,0.673
M2 = {0+5/2,2+2/23 = {2.5,13
& = [(0-2.17)2 + (0-0.67)2 + (5-2.17)2 +
(2 -0.67)2 + (1.5 -2.17)2 + (0 -0.67)2 ] =15.83
&2
=14.5
e2 =15.83 +14.5 =30.33
step 2 -计算质心到样本的距离，并取距离最小
的重新分配到簇。
P(M1，？）
=[(0-2.17)2 + (0-0.67)2]1T =2.27
P(M2,?) = 2. 69 => ? / C1
P(M1,?) =3. 12
P(M2,?) =2. 69 =>?/C2
P(M1,?) =0. 95
P(M2,?) =1.414 =>?/C1
P(M1,?) =2. 54
P(M2,?) =2. 69 =>?/C1
P(M1,?) =2. 91
P(M2,?) =2. 69 =>? /C2
step 3 -根据重新分配的簇
,计算新质心。
C1 =(?,?,?) C2 = (?,?)
M1 = {0.5,0.673 M2 = {5,1 (
相应的方差是
-e2 =4.166 7 +2 =6.166 7
第一次迭代后，总体误差显著减小（由
30. 33减
小到
6.166 7)，算法终止。
!2 EM算法
EM 算法
（Expectation Maximization Algorithm)*4]
是一种逐次逼近算法，包括计算期望值和求极大值，
主要运用高斯混合模型的参数估计。该模型可以解
决聚类分析、机器学习等领域中的许多实际问题。
该算法的步骤如下：
Input -观测数据
(5 ,5 '…，5 )'高斯混合模型
Output-高斯混合模型参数(1) 取参数的初始值，开始迭代。
(2) 求期望值。依据当前模型参数，计算
lgP(5y+,的期望，即
N(,,0) =:[lgF(5/VI) I
5,)]。
(3) 求极大值。求函数
N(,,')对，的极
大值，即计算新一轮迭代的模型参数
-,(I+1)=
argmaxN(,，,('）。
(4) 重复第（
2)步和第（
3)步，直至收敛，即直
到对数似然函数值，不再有明显的变化为止。
! 3 DBSCAN 和
FarthestFirst 算法
DBSCAN( Density - Based Spatial Clustering Ap
plication with Noise)算法是一种经典的基于密度的
聚类算法，用于过滤噪声数据
,实现快速发现任意形
状的类的分析
[5]。执行流程
:扫描数据库，找到每个
点的邻居个数
e。如果
e大于阈限值，则该记录作为
中心记录，随即以这个记录为中心的类就产生了
[6]。
DBSCAN算法使用欧式距离度量，确定哪些实例属
于哪个簇。与
X均值算法不同，
DBSCAN算法可以
自动确定簇的数目，发现任意形状的簇，并纳入离群
概念。
FarthestFirst算法是快速地近似
X均值的聚类
算法，每一次取最远的那个点。该算法主要包括
2
个部分
-FarthestFirst遍历和层次聚类。
FarthestFirst
遍历的思想类似于构造一棵最小生成树（针对点到
集合）。算法过程如下
[7]-
Input-n data points wtli a distance metric d(. ”）
Pick a point and label it 1
For' =2，
3，
•••，
,
Fint the point furthest from { 1,2，…,'-1 ( and
label it
Let '(i)
= argmin j P( i,j) . Let 8 = P(''(') 2 WEKA平台下的聚类过程 怀卡托智能分析环境（ Waikato Environment for Knowledge Analysis,缩写为 “WEKA”），是 一 ■种使用 Java语言编写的数据挖掘机器学习软件，其中包括 处理标准数据挖掘问题的所有方法，如分类、回归、 聚类、关联规则以及在新的交互式界面上的可视化。 WEKA是开放源代码，新编写的算法只要符合其接 口规范，就可以嵌入其中，从而扩充其原有算法。 以 K - means算法为例，介绍在 WEKA平台下 如何聚类。 WEKA平台把 K- means算法的实现命 名为 “ SimpleKMeans ” 算法，位于 weka. clusterers. SimpleKMeans包中。以此构建聚类器，包括以下 4 • 91 •