图2-1 第一对簇更“紧密”
2.1.2 相对紧密度(Relative Closeness,RC)
簇 和 间的相对紧密度被定义为用簇 和 的内部紧密度规格化簇 和 间的绝对紧密度。度量两个簇的紧密度的方法是取簇 和 间连接边的平均权重。具体计算公式如下:
 
式中, 为簇 和 间的绝对紧密度,通过簇 和 的连接边的平均权重来度量,即 , 是内部紧密度,通过簇 内连接边的平均权重来度量,即 。
RI和RC可以用多种不同的方法组合,以产生自相似性(self-similarity)的总度量。 Chameleon使用的是合并最大化 的簇对,其中 是用户指定的参数,通常大于1。
2.1.3 Chameleon算法关键步骤
Chameleon算法由三个关键步骤组成:稀疏化,图划分和子图合并,如图2-2所示。
图2-2  Chameleon算法聚类步骤
Chameleon算法具体描述如下:
<1> 构建稀疏图:由数据集构造成K-最近邻图集合 。
<2>多层图划分:通过一个多层图划分算法将图 划分成大量的子图,每个子图代表一个初始子簇。
<3>合并子图:合并关于相对连接度和相对紧密度而言,最好的保持了簇的自相似性的簇。
<4>重复步骤<3>,直至不再有可以合并的簇或者用户指定停止合并时簇的个数。
三个关键步骤进一步说明如下
1.构建稀疏图:图的表示基于K-最近邻方法,节点表示数据项,边表示数据项间的相似度,节点v,u之间的边表示节点v在节点u的k个最相似点中,或节点u在节点v的k个最相似点中,或节点u在节点v的k个最相似点中。使用图的表示有以下优点:
①距离很远的数据项,完全不相连。
②边的权重代表了潜在的空间密度信息。
③在密集和稀疏区域的数据项都是同样能建模。
④表示的稀疏便于使用高效的算法。
2.多层图划分:基于得到的稀疏图,使用如HMETIS等有效的多层图划分算法来划分数据集,划分步骤如下:
<1>从得到的稀疏图开始。
<2>二分当前最大的子图。
<3>直到没有一个簇多于MIN—SIZE个点(MIN—SIZE是用户指定的参数)。
3.合并子簇:采用凝聚层次聚类方法合并子簇。合并子簇有以下两种方法。
方法一:设阀值,预先设定两个阀值,只TRI和TRC只有满足条件
RI{ , }≥TRI且RC{ , }≥TRC 时,子簇才会被合并。
方法二:簇间的相似度采用函数 ,即取相对互连性和相对近似性之积最大者合并。
Chameleon算法能够有效的聚类空间数据,能识别具有不同形状,大小和密度的簇,对噪声和异常数据不敏感。Chameleon算法的时间复杂度为 ,因此使用Chameleon算法对中小规模数据集的聚类分析是个很好的选择,但对于在大规模数据集其应用受到了限制。
2.2 K-means算法
2.2.1 算法简介
为了便于与Chameleon算法对比,我们简单介绍下K-means算法:K-means算法是1967年由MacQueen首次提出来的一种经典算法,迄今为止,很多聚类任务都选择该算法。K-means聚类算法的处理流程如下:首先,随即选择K个对象,每个对象代表一个簇的初始均值或中心;对于剩余的每个对象,根据其与各簇中心的距离,将他指派到最近(或最相似)的簇,然后计算每个簇的新均值,得到更新后的簇中心;不断重复,直到准则函数收敛。通常,采用平方误差准则,即对于每个簇中的每个元素,求对象到其中心距离的平方和,这个准则试图使生成的K个结果簇尽可能的紧凑和独立。
K-means聚类算法分形式化描述如下:
---------------------------------------------------------------------
算法:K-means
上一篇:网络图像搜索中的图像摘要技术研究
下一篇:ASP.net教学进度管理系统设计与实现+ER图

基于Apriori算法的电影推荐

PHP+IOS的会议管理系统的设计+ER图

数据挖掘在电子商务中的应用

数据挖掘的主题标绘数据获取技术与实现

基于PageRank算法的网络数据分析

基于神经网络的验证码识别算法

基于网络的通用试题库系...

10万元能开儿童乐园吗,我...

中国学术生态细节考察《...

医院财务风险因素分析及管理措施【2367字】

志愿者活动的调查问卷表

神经外科重症监护病房患...

AT89C52单片机的超声波测距...

承德市事业单位档案管理...

国内外图像分割技术研究现状

C#学校科研管理系统的设计

公寓空调设计任务书