文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 2基于分层聚类的k_means算法
侵权投诉

2基于分层聚类的k_means算法

数据挖掘算法

8河海大学常州分校学报2007年3月1.2k!means聚类算法

划分法的主要思想是对一个有n个对象的数据集,构造k个分组(k<n),每一个分组代表一个类.对于给定的k,首先给出一种初始的分组方法,然后通过反复迭代来改变分组,使每一次改进之后的分组方案都较前一次的好.在划分法中k!means算法因其算法执行速度较快而且便于理解,已成为一种最为普遍的算法[4],k!means聚类算法的步骤为

a.按一定原则选择n个对象作为初始的聚类中心.

b.根据聚类中心的值,将每个对象赋给距其最近的类.

c.更新聚类中心,重新计算每个类中对象的平均值,用对象的均值点作为新的聚类中心.

d.重复执行步骤b、c,直到各个类不再发生变化.

对于聚类质量可用误差平方和准则函数进行测试,最佳聚类结果对应于目标函数的极值点.由于目标函数存在许多局部极小点,而算法的每一步都是沿着目标函数减小的方向进行,因此若在初始化时解落在某个局部极小点附近,就会使算法在局部极小点处收敛.可见初始聚类中心的随机选取可能会陷入局部最优解,而难以获得全局最优解.除此之外k!means聚类算法的不足之处还表现在:(a)类的数目k必须在聚类执行之前确定;(b)聚类有可能将邻近对象的选择作为不同的类中心点;(c)对孤立点较为敏感.

2混合算法

针对传统聚类算法存在的优缺点,提出一种混合算法———基于分层聚类的k!means算法,该算法结合了分层聚类和k!means聚类算法的优点,同时也克服了它们原来的缺点.算法的思想方法是首先进行分层聚类,得到一些初始信息,然后运用k!means算法进行精化,最后得到质量较高的聚类结果.

2.1相似度测量

在聚类分析时,经常需要计算对象间的相似度(或相异度),相似度常用对象间的距离来表示.最常用的距离度量方法有欧几里得距离、曼哈坦距离和明考斯基距离,在混合算法中用欧几里德距离,其定义为

(1)d(i,j)=!i1j1i2j2ipjp式中,(xi1,xi2,…,xip)和(xj1,xj2,…,xjp)是2个p维的数据对象.

2.2算法参量

a.描述每个类的聚类特征F=(n,m).其中n为类内的数据点的个数,它反映了类的大小;m为n个数据点的均值,它反映了该类中心的位置.

b.描述层次聚类在整个算法过程中所占的比例ε.即层次聚类算法的运行时间与整个算法运行时间的比值.

2.3具体算法过程

基于分层聚类的k!means算法的实现过程具体分为2个阶段.在第1阶段,通过分层聚类获得初始聚类信息,包括类的个数和初始中心点的位置.算法描述如下:

a.用p维向量Xi=(xi1,xi2,…,xip)(i=l,2,…,n),描述n个待聚类的数据点,这n个p维向量构成一个n行p列的数据矩阵DATA.

b.计算数据点间的相似度,即它们两两间的距离,找出距离最小的2个数据点,并将它们合并为一个类.c.计算这2个数据点的平均值,作为新的类的中心点;用聚类特征Fi=(ni,mi)(i=l,2,…,k)描述新类.

,结束分层聚类.d.重复步骤b和c,直到达到了用户预定义的分层聚类所占的百分比ε

e.对通过以上步骤获得的各个类,都用聚类特征Fi(i=l,2,…,k)表示,分别计算这些类的中心mi(i=1,2,…,k),并将其作为进行k!means算法的初始的类中心点.

在第2阶段,通过k!means聚类算法精化初始结果,算法如下:

f.考察DATA矩阵中的每个数据点,若该数据点已在步骤b中出现,则不予处理,否则计算这个数据点与各个类中心mi(i=l,2,…,k)的距离,找出最小距离,并将该数据点赋给离它最近的类.

g.重新计算每个类的数据点的平均值和类中数据点的个数,更新类的聚类特征值.

h.重复步骤f和g,直到类中成员都不发生变化.

上一页第2页

你可能喜欢

热门文档

相关文档

  • 基于聚类分析的K_means算法研究及应用

    M ay 2007 基于聚类分析的 K means算法研究及应用张建萍 , 刘希玉 1 2 * ( 1. 山东师范大学 信息科学与工程学院, 山东 济南 250014; 2. 山东师范大学 ...

  • 基于K_means聚类算法的校园网用户行为分析研究

    2 1 1 ( 1 南京农业大学工学院网络中心 南京 210031 2 南京农业大学研究生院...基于 K - means算法以校园网用户行为特征为对象来进行聚类 分析 ,提出了几个...

  • 基于k_means聚类算法的试卷成绩分析研究

    基于k_means聚类算法的试卷成绩分析研究基于k_means聚类算法的试卷成绩分析研究...2 基于 k2means 聚类算法的试卷成绩分析出区分不同组的有用特征 . 2. 1 数据...

  • 基于K_Means和EM算法的聚类分析

    基于K_Means和EM算法的聚类分析_自然科学_专业资料。2009 年第 2 期 福 建 电 脑 79 【摘要】: 本文叙述了 K-Means 算法和 EM 算法的基本原理及性质,...

  • 基于分层聚类的K-MEANS 算法

    基于分层聚类的K-MEANS 算法_自然科学_专业资料。特别说明此资料来自豆丁网(... 8页 1下载券 K-MEANS聚类算法研究 2页 免费喜欢此文档的还喜欢...

  • 基于聚类分析的 K-means 算法研究及应用

    24, No. 5 May 2007 基于聚类分析的 K-m eans 算法研究及应用 * 张建萍 , 刘希玉 1 2 ( 1. 山东 师范 大学 信 息科 学与 工程学 院, 山东 济南 ...

  • 一种基于K_means的自适应聚类算法的研究

    ◇ 职业教育 ◇ 2012 年第 02 期 一种基于 K- means 的自适应聚类算法的...2.3 对改进 k-means 算法的描述 结合以上分析,给出改进的 k-means 算法流程...

  • 基于k_means的中文文本聚类算法

    978-1-61284-040-6/10/$26.00 ?2010 IEEE 9 SSME2010 本文余下部分的主要内容是:第 2 节详细分析并改进 基于 k-means 的中文文本聚类算法;第 3 节对...

  • K_means聚类算法研究

    ( 1. 大连海洋大学信息工程学院, 辽宁大连 116023; 2. 黑龙江工程学院土木与建筑工程学院, 黑龙江哈尔滨 150050) 要] K- means 算法作为聚类分析 算法, 已被...

  • 一种基于遗传算法的K_means聚类算法

    means 算法是聚类分析中一种基本的划分方法,因其算 法简单、理论可靠、收敛... 2 基于遗传算法的 K-means 聚类算法( GKA ) GKA 的基本思想是:首先从要...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email