0
引言
数据库和信息技术的研究与发展以及获取数
据手段的多样化，人们所拥有的数据量急剧增加，
数据挖掘⋯引起了信息产业界的极大关注，其主
要原因是存在大量数据，可以广泛使用，并且迫切
需要将这些数据转换成有用的信息和知识．数据
挖掘是从大型数据库或数据仓库中提取出可信、
新颖、有效，并能被人理解模式的高级处理过程。
可广泛应用于决策支持、信息管理、科学研究等领
域．数据挖掘的任务包括分类预测、关联规则分
析、聚类分析、时间序列模式和偏差分析等．其中
聚类分析是研究与应用的热点之一，也是数据挖
掘领域的一个重要分支．聚类就是一个将数据集
划分为若干簇或类的过程，通过聚类使得同一类
内的数据对象具有较高的相似度，而不同类中的
数据对象具有较高的相异度．
聚类算法¨·大体可以划分为如下几类：划分
的方法"’、层次的方法、基于密度的方法、基于网
格的方法、基于模型的方法、基于遗传算法的方
法、基于蚁群算法的方法等．参考文献[4]对以上
各种聚类算法的性能与适用范围做了分析．
1 k_means算法
1．1
k_means算法的思想
k_means算法以k为参数，把／’t个对象分成k
个簇，以使簇内具有较高的相似度，而簇间的相似
度较低．相似度的计算根据一个簇中对象的平均
值来进行．相似度的定义是划分的关键．
k_means"1算法的基本思想是：随机地选择k
个对象，每个对象初始地代表了一个簇的平均值
或中心．对剩余的每个对象，根据其与各个簇中心
的距离，将它赋给最近的簇．然后重新计算每个簇
的平均值．这个过程不断重复，直到目标甬数收
敛．通常定义为公式(1)的目标函数，采用启发式
方法使得目标函数值最小．
^
E=y y P—m；I (1)
篇“P“i
’
式中：层为集合u中所有对象与相应聚类中心的
均方差之和；p为对象空间中一个数据对象；mi为
类C。的均值(P和m；都是多维的)．该函数旨在使
生成的聚类结果簇尽可能地紧凑和独立．
由于该方法在聚类过程中采取距离就近原
则，在实际应用中，不考虑数据样本中的每个属性
变量在聚类过程中的不同作用，而是将它们统一
看待．用样本之间的欧氏距离并不能准确地表示
相似度，因为相似不仅仅依赖于样本间的相近程
度，还依赖于数据样本间的内在性质，也就是说数
据集中每个属性在聚类分析过程中对于数据样本
划分的重要性不同．
1．2 k means算法的一般过程
k—means算法属于划分方法，它需要有先验
收稿日期：2009—09—06；修订日期：2009一11—15
基金项目：兰州市企业技术攻关计划资助(2009一I一4)；兰州交通大学“青蓝”人才工程基金资助(QL一05一IOA)
作者简介：张忠林(1965一)，男，河北阜城人，兰州交通大学教授，博士，主要研究方向：智能信息处理、软件工程，
E—mail：zhangzl@mail．1zjtu．cn；曹志字(1983一)，男，内蒙古包头人，硕士研究生，主要研究方向：数据挖掘．
万方数据
郑州大学学报(工学版) 2010年
知识k，即知道数据对象集合要聚为几类．在此，
笔者给出k means算法的一般过程．
设两个P维向量菇l=(髫fl’并讫，⋯，戈币)和戈，=
(和，稚，⋯，靠)分别表示两个对象，它们的欧氏
距离为：
d(髫i，菇，)=
(2)
下文介绍k_means算法的一般过程．
算法输入：聚类个数k，以及包含n个数据对
象的数据样本集U；
算法输出：满足方差最小标准的k个聚类．
算法步骤：
(1)从厅个数据对象中任意选择k个对象作
为初始聚类中心；
(2)根据每个聚类中所有对象的均值(中心
对象)，计算样本集中每个对象与这监中心对象
的欧式距离，并根据最小距离重新对相应对象进
行划分；
(3)重新计算每个(有变化)聚类的均值(中
心对象)；
(4)循环执行(2)到(3)，直到每个聚类不再
发生变化为止．
2
基于加权欧式距离的k_means算法
2．1
变异系数赋权法
数据样本集用可分性较好的数据样本来描
述，具有相同类别的数据样本越集中，而不同类
别的数据样本越远离，表现在散点图上就是数据
点的分散性比较好，而且类与类之间的距离比较
大．为了反映数据的离散程度，通过对多种赋权法
的比较，选用变异系数作为其权值．定义如下：【51
变异系数赋权法是在方差倒数赋权法的基础
上提出的．一组数据的变异系数是它的标准差除
以均值的绝对值．即对数据集中的n个数据石。，
菇2，⋯⋯，并。．记为
’
n
；=土∑置
(3)
n—t
I
’
^
s，=(击荟(xr一∽寺
(4)
则
移，=S，／I戈I
(5)
就是茗。，茗：，⋯⋯，茹。的变异系数．
于是，对数据库中选用的属性：。，z：⋯⋯，：，，
利用被评价对象的数据，各个属性都有各自的变
异系数．为了方便，用q表示乞的变异系数。i=l，
2，⋯，P，此时，属性：i相应的权重系数埘；：
p
彬；=vi／∑％i=1，2，⋯，P
(6)
I=I
口i的值大表示算。在不同的对象身上变化大，
区别对象能力强，所以应给予重视．
2．2
加权欧式距离的k_means算法
基于加权欧式距离的k_means算法的基本思
想是在给出待测数据库以后，首先计算数据集中
各个属性的权值，再计算数据样本之间的相似度
时使用加权欧式距离，即：
d(髫；，≈)=
~／埘I(茗n一和)2+埘2(戈垃一稚)2+⋯+埘p(髫．；P一％)2
(7)
下文为改进算法的一般过程．
算法输入：聚类个数k，以及包含／7,个数据对
象的数据样本集U．
算法输出：满足方差最小标准的k个聚类．
算法步骤：
(1)从It个数据对象中任意选择k个对象作
为初始聚类中心；
(2)根据每个聚类中所有对象的均值(中心
对象)，计算样本集中每个对象与这些中心对象
的加权欧式距离，并根据最小的加权欧式距离重
新对相应对象进行划分：
(3)重新计算每个(有变化)聚类的均值(中
心对象)；
(4)循环执行(2)到(3)，直到每个聚类不再
发生变化为止．
3：
与传统的k_means算法的比较
基于加权欧式距离的k_means算法与传统的
k_means算法相比较，就是把传统算法中计算样
本点与类间相似度的欧氏距离变成了这里的加权
欧氏距离，计算加权欧式距离中的权值会花费一
定的时间，但是它对数据集中样本的处理能力却
大大提高了．在处理数据的实际过程中，对“噪
声”和孤立点样本不是十分敏感，少量该样本不
会对权重系数的选取产生大的影响．该算法的复
杂度和传统算法是一致的，也是0(nkt)，其中：n
是数据集中所有样本的数目；k是簇的数目；t是
迭代的次数．因此当k《n且t《n时，对处理大
数据集是可伸缩的和高效率的．另外，该算法和传
统算法一样都需要事先估计簇的个数k，如想得
到最优解时必须试探不同的k值．
万方数据
第l期 张忠林。等：基于加权欧式距离的k_means算法研究 91
4
实验分析
为了验证改进的效果，笔者对传统的k—
means算法、基于加权欧式距离的k—means算法
进行了对比实验．实验的平台是Windows XP。P4
2．8 GHz CPU，512 MB内存，80 GB硬盘．开发工
具采用VC++6．0．选用UCI数据库上的Iris、
Wine、Balance—scale、New—thyroid、Haberman五
组数据集作为测试数据．UCI数据库是一个专门
用于测试机器学习、数据挖掘算法的公共数据库，
库中的数据都有确定的分类，因此可以用准确率
直观地表示聚类的质量．整个实验过程中，对于传
统的k_means聚类算法，选取不同的初始聚类中
心，运行10次，和基于加权欧式距离的k—means
算法进行比较．如表1所示．
裹1传统k—means算法与基于加权欧式距
离的k—means算法实验结果
Tab．1 The resules between the traditional k means
algorithm
and the euclid distance with
weights of k—means algorithm
Iris数据集包含150条样本记录，分别取自三
种不同的鸢尾属植物Setosa、Versieolor和Virgini．
ca的花朵样本，每一类各50条记录，其中每条记
录有4个属性：萼片长度(Sepal length)、萼片宽
度(Sepal width)、花瓣长度(Petal length)和花瓣
宽度(Petal width)．它们的取值范围分别为：(4．3
—7．9)，(2．0—4．4)，(1．0—6．9)，(0．1—
2．5)．所对应的权值分别为：0．126、0．125、0．196、
0．552．可以看出，同一个属性中的样本取值范围
较为接近时，这个属性所对应的权值也较小；相
反，同一个属性中的样本取值范围较大时，对应的
权值也较大．在利用改进后的k—means算法来计
算样本相似度时，加权欧式距离可以比较准确地
代表它们的数据分布，所以对数据集的划分也较
为准确，最终得到了很好的聚类结果．
Wine数据集中的数据为产于意大利同一地
区不同种植园的3种葡萄酒的成分分析样本，包
含178条样本记录，分成3类，每个数据项有13
个属性，各个属性的取值范围差距较大。可由这些
属性确定葡萄酒出产的种植园．经过分析发现：对
分类最为重要的包括3个属性：Alcohol，Fla．
vanoids，Color_intensity，它们的取值范围分别为：
(0．34—5．08)，(1．28一13)，(11．03～14．83)，而
对分类贡献不大的属性Proline的取值范围是
(278—1 680)，在计算距离时，属性Proline起到
了绝对的作用，从而导致用欧氏距离来计算样本
间的相似度并不能很好地代表数据的实际分布情
况．所以传统的k_means算法在对Wine数据集进
行处理的过程中，受属性Proline影响，样本间相
似度的计算产生了巨大的偏差，最终的聚类结果
不令人满意，仅有62．47％．在引入加权欧式距离
来计算相似度后，可以减少属性Proline对数据样
本的影响．
传统的k_means算法没有考虑到数据的实际
分布情况，而只是给出了一个算法可以运行的必要
条件(把样本间的欧式距离作为相似度)．应用改
进后的算法，由于在一开始就计算得到了各个属性
的权值，并将权值引入到计算欧式距离的过程中，
所以得到了一个较为准确的样本间的相似度，在所
选的五组数据集中，加权后有三组数据的准确率较
传统算法的准确率获得明显上升，Balance—scale、
Haberman数据的准确率也略微有所提高．
5
结论
传统欧氏距离的计算方法，认为数据集中的
所有属性在聚类中作用是相同的，用这种方法计
算的欧式距离不能够准确反映样本之间的相似度
基于这种情况，笔者提出的基于变异系数加权欧
氏距离的计算方法，通过加权充分体现各个属性
在聚类中的重要性，从而提高聚类结果的准确性
和有效性．实验结果表明，变异系数加权欧氏距
离的方法克服了传统欧氏距离在聚类算法中的缺
陷，优化了算法的性能．