基于网格的聚类方法研究.docx
《基于网格的聚类方法研究.docx》由会员分享,可在线阅读,更多相关《基于网格的聚类方法研究.docx(14页珍藏版)》请在咨信网上搜索。
1、基于网格的聚类方法研究摘要:已有的聚类算法对于发现任意形状的聚类和处理离群点效果不理想,分析了现有基于网格的聚类算法。使用网格方法的数据分析方法将空间划分为由(超)矩形网格单元组成的网格,然后在网格单元上进行聚类。最后,总结全文并提出基于网格的聚类需要进一步研究的方向。关键词:数据挖掘;网格;聚类1 引言数据挖掘是指从大型数据库或数据仓库中提取隐含的、未知的及有应用价值的信息或模式。它是数据库研究中的一个很有应用价值的领域,融合了数据库、机器学习、统计学等多个领域的理论和技术1。聚类分析是数据挖掘中广为研究的课题之一,是从数据中寻找数据间的相似性,并依此对数据进行分类,从而发现数据中隐含的有用
2、信息或知识。目前已经提出了不少数据聚类算法,其中比较着名的有CLARANS、BIRCH、DBSCAN和CLIQUE等。但对于高维、大规模数据库的高效聚类分析仍然是一个有待研究的开放问题。网格方法是空间数据处理中常用的将空间数据离散化的方法。基于网格的聚类算法由于易于增量实现和进行高维数据处理而被广泛应用于聚类算法中。研究人员已经提出了很多基于网格的聚类算法,包括STING,它利用了存储在网格单元中的统计信息;WaveCluster它用一种小波转换方法来聚类数据对象;CLIQUE在高维数据空间中基于网格和密度的聚类方法等。本文对已有的基于网格的聚类算法进行了研究,从网格的表示,划分网格单元的方法
3、,到统计网格内信息,搜索近邻网格单元,聚类超过指定阙值的网格单元的各个步骤进行了分析,最后对基于网格方法聚类的研究方向做了展望。2 网格的定义与划分网格的基本概念,设A1, A2, Ar 是数据集O=O1, O2, On 中数据对象的r 个属性的有界定义域,那W=A1 A2 Ar 就是一个r 维空间, 将A1,A2 , Ar 看成是W 的维( 属性、字段),则对于一个包含n 个数据点的r 维空间中的数据集O=O1 , O2 , On ,其中Oi =Oi1 , Oi2 , Oir ( i=1, 2, n) , Oi 的第j 个分量Oij Aj 。将W的每一维M等分,即把W分割成个网格单元。基于网
4、格聚类算法的第一步是划分网格结构,按搜索子空间的策略不同, 主要有基于由底向上网格划分方法的算法和基于自顶向下网格划分方法的算法。由底向上的划分方法由底向上的网格划分方法按照用户输入的划分参数(即每维段数ki,1 i d),将数据空间均匀划分为相等大小的网格单元,假设落入同一网格单元内的所有数据点都属于同一个簇,每个网格单元保存落入其内数据的统计信息,比如数据点个数,数据点之和。包含一定数目数据点的网格单元被称为高密度网格单元。WaveCluster与CLIQUE是采用由底向上网格划分方法的代表性算法。WaveCluster处理低维空间数据,它的性能超越了BIRCH、CLARANS,与DBSC
5、AN等优秀的聚类算法15。CLIQUE考虑了高维子空间聚类,但它的时间复杂度较高,需要用户指定全局密度阈值。算法MAFIA对CLIQUE进行了改进,为了减少聚类算法需要处理的网格单元数目,MAFIA将均匀划分网格中每一维上数据分布密度相似的相邻段合并,由此得到一个不均匀划分的网格。这个网格在数据分布较均匀的区域划分粒度大,在数据分布不均匀的区域划分粒度小,这种不均匀划分网格的方法能够提高聚类的质量,被后续的许多算法所采用。采用由底向上的网格划分方法的优点在于,它能通过对数据的一遍扫描,将数据压缩到一个网格数据结构内,并基于这个网格数据结构,发现任意形状的簇。此外,如果网格单元的粒度较小(即体积
6、较小),那么得到的聚簇的精度较高,但是算法的计算复杂度较大。此外,由底向上的网格方法存在不适合处理高维数据的问题。在高维空间,数据的分布是非常稀疏的,网格方法失去其压缩作用,而且属于同一个簇的高密度网格单元也可能不相连,这使聚类算法不能发现合理数目的簇。自顶向下的划分方法自顶向下的网格划分方法采取分治的策略(divide and conquer principle),对数据空间进行递归划分,使问题的规模不断减小。首先将原数据空间划分为几个较大的区域。对于每个得到的区域,划分过程反复执行,直到每个区域包含属于同一个簇的数据点,那么这些区域就是最终的网格单元。基于自顶向下网格方法的聚类算法直接将高
7、密度网格单元识别为一个簇,或是将相连的高密度网格单元识别为簇。OptiGrid与CLTree10是两个典型的基于自顶向下网格划分方法的聚类算法。其中, OptiGrid则是用空间数据分布的密度信息来选择最优划分。通过一个密度函数来决定切割平面,可以将数据空间划分为规则的或不规则单元,与传统的等间距的划分相比,可以用此来解决高维聚类的问题。而CLTree用划分后的信息增益来选取最优划分。自顶向下划分方法的主要优点在于不需要用户指定划分参数,而是根据数据的分布对空间进行划分,因此这种划分更为合理。数据空间维度对自顶向下网格方法的影响较小,可以快速将大型高维数据集中的簇分隔开。这一类方法的计算复杂度
8、与数据集大小和维度都呈线性关系适合于处理高维数据。由于划分是基于数据分布的,而通常认为噪音是在整个空间均匀分布的,所以自顶向下划分方法对噪音不敏感。但是,由于这种方法得到的网格单元的体积远大于由底向上网格方法中的网格单元体积,因此方法产生的簇的描述精度比由底向上的网格方法得到的簇的描述精度要低。而且在自顶向下的划分过程中,同一个簇可能被划分到不同的区域中,最终得到的同一区域也可能包含不同的簇,这样就进一步降低了算法的正确度。这类划分方法的另一个缺点是它在划分过程中,需要对数据集进行多次扫描。而由底向上划分方法在于只需对数据集进行一次线性扫描以及较高的簇的描述精度。因此,两类方法适用于不同的问题
9、。前者适于处理高维数据集,后者能有效处理存取代价较大的超大型数据集与动态数据。3 基于网格的聚类过程基于网格的聚类算法的基本过程是,首先将数据空间W划分为网格单元,将数据对象集O 映射到网格单元中,并计算每个单元的密度。根据用户输入的密度阈值MinPts 判断每个网格单元是否为高密度单元,由邻近的稠密单元组形成簇11,如表1。 算法1中的步骤1已经在上文详细说明,下面具体介绍步骤2-4的内容。网格单元的密度簇就是一个区域,该区域中的点的密度大于与之相邻的区域。在网格数据结构中,由于每个网格单元都有相同的体积,因此网格单元中数据点的密度即是落到单元中的点的个数。据此可以得到稠密网格单元的密度是,
10、设在某一时刻t一个网格单元的密度为density,定义density=单元内的数据点数/数据空间中总的数据点数,设密度阈值为, 为用户输入的密度阙值,当density 时,该网格单元是个密集网格单元。相对于稠密网格单元来说,大多数的网格单元包含非常少甚至空的的数据,这一类网格单元被称为稀疏网格单元。大量的稀疏网格单元的存在会极大的降低聚类的速度,需要在聚类之前对稀疏网格单元进行处理,定义稀疏密度阈值为,当density时,该网格单元是个稀疏单元。对于稀疏网格单元的处理方法一般采用压缩的方法或者直接删除的方法,如果需要保留稀疏网格单元用于后续处理,可以使用压缩的方法;如果在现有数据的基础之上直接
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 网格 方法 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。